\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{booktabs,array}
\usepackage{microtype}
\usepackage{xcolor}
\usepackage[colorlinks=true,linkcolor=blue!55!black,citecolor=blue!55!black,urlcolor=blue!55!black]{hyperref}
\hypersetup{
 pdftitle={The Exact Junta Bound for Degree-Two Boolean Functions on q-ary Hamming Cubes},
 pdfauthor={Yuran Xiu},
 pdfsubject={Relevant variables and structure of quadratic Boolean functions on finite product spaces},
 pdfkeywords={junta theorem, relevant variables, degree-two Boolean functions, quadratic Boolean functions, q-ary Hamming cube, query complexity}
}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\R}{\mathbb R}
\newcommand{\E}{\mathbb E}
\newcommand{\rel}{\operatorname{Rel}}
\newcommand{\Inf}{\operatorname{Inf}}
\newcommand{\ind}{\mathbf 1}
\newcommand{\lean}[1]{\texttt{\small\detokenize{#1}}}
\title{The Exact Junta Bound for Degree-Two Boolean Functions\\on \texorpdfstring{$q$}{q}-ary Hamming Cubes}
\author{Yuran Xiu\\IIIS, Tsinghua University\\
\texttt{xiuyr23@mails.tsinghua.edu.cn}}
\date{14 October 2026}

\begin{document}
\maketitle

\begin{abstract}
We determine the maximum number of relevant variables of a Boolean function
of degree at most two on a finite alphabet. For every integer $q\geq2$,
this maximum is exactly $\max\{4,q+1\}$. Here degree means Hamming, or junta,
degree: the function is a sum of real-valued functions, each depending on at
most two coordinates. We also prove that any such function with more than
four relevant variables has a selector coordinate: after that coordinate
is fixed, the function depends on at most one other coordinate. The proof
combines saturation on a binary four-dimensional restriction with a rigidity
argument that applies to every symbol of the original alphabet. Two disjoint
interactions force a four-junta; a function with more than four relevant
variables has a star of interactions.
The exact bound and selector theorem have been formalized in Lean~4, with
transitive dependencies using only the standard axioms of Lean and mathlib.
\end{abstract}

\section{Introduction}

A Boolean function on a product space may be given as a sum of terms that
each involve only a few coordinates. How many coordinates can affect its
output? This is the junta problem for bounded-degree Boolean functions.
Write $R_{d,q}$ for the largest possible number of relevant coordinates of a
Boolean function on $[q]^n$, over all dimensions $n$, whose Hamming degree
is at most $d$. We use $[q]=\{1,\ldots,q\}$ and give a definition of degree
that does not require an algebraic structure on the alphabet.

\begin{definition}\label{def:degree}
A real-valued function has \emph{degree at most $d$} if it is a finite sum of
real-valued functions, each depending on at most $d$ coordinates. A coordinate
$i$ is \emph{relevant} for $f$ if there exist inputs $x,y$ differing only at
$i$ with $f(x)\ne f(y)$. Let $\rel(f)$ be the set of relevant coordinates.
A function with at most $r$ relevant coordinates is an $r$-junta.
\end{definition}

For a cyclic alphabet, this degree is the maximum support size of a nonzero
Fourier character. It counts the number of coordinates in an interaction,
rather than the ordinary total exponent after symbols are represented by
integers. In particular, every unary function has degree at most one.
Constants and linear terms are permitted throughout.
The Fourier equivalence follows directly from orthogonality: a function
depending on a set $S$ has no Fourier coefficient on a character involving
a coordinate outside $S$, and a character depends only on its support.
For a real-valued function, taking real parts of the Fourier expansion
gives real-valued summands with the same support bounds. This is also the
finite-sum definition used in~\cite[Definition~2]{Val26}.

\begin{theorem}[Exact junta bound]\label{thm:exact}
For every integer $q\geq2$, every $n\geq0$, and every Boolean function
$f:[q]^n\to\{0,1\}$ of degree at most two,
\[
 |\rel(f)|\leq\max\{4,q+1\}.
\]
For every $q\geq2$, equality is attained by a function on exactly
$\max\{4,q+1\}$ coordinates. Thus
\begin{equation}\label{eq:exact}
 R_{2,q}=\max\{4,q+1\}.
\end{equation}
\end{theorem}

The upper bound follows from a structural alternative.

\begin{theorem}[Selector structure]\label{thm:selector}
Let $A$ be a finite nonempty alphabet, and let $f:A^n\to\{0,1\}$ have
degree at most two. If $|\rel(f)|>4$, there exists a coordinate $i$ such that,
for each $a\in A$, the section $f|_{x_i=a}$ depends on at most one coordinate
other than $i$.
\end{theorem}

The remaining coordinate may depend on $a$, and a section may be constant.
Consequently such a function can be evaluated by first querying the selector
and then, if needed, querying one additional coordinate. The statement does
not assert a two-query algorithm for the four-junta alternative.

\paragraph{Prior work.}
The binary case $R_{2,2}=4$ is classical. Filmus gives an explicit
classification of quadratic Boolean functions on the binary
cube~\cite{Filmus22}. Mogilnykh and Valyuzhenich classify equitable
two-partitions of Hamming graphs associated with the second
eigenvalue~\cite{MV20}. For Boolean functions, their setting restricts the
spectrum to levels $0$ and $2$. The present theorem allows arbitrary
level-one terms, and makes no equitability or balance assumption.

For general degree and $q\geq3$, Valyuzhenich proved
$R_{d,q}\leq dq^{d+1}/(4(q-1))$~\cite{Val24}. More recently, he proved
\begin{equation}\label{eq:previous}
 R_{d,q}\leq m_q q^d,
 \qquad m_q=\frac{2q(q^2+4q+1)}{(q-1)^4},
\end{equation}
with improved constants for several small alphabets~\cite{Val26}.
At degree two,~\eqref{eq:previous} is $2q+O(1)$ as $q\to\infty$.
The addressor construction giving $R_{2,q}\geq q+1$ is also recorded
in~\cite{Val26}. Our contribution is the exact unrestricted degree-two
bound and the selector alternative. The binary saturation argument and
the matching constructions are known ingredients.

\paragraph{Proof overview.}
The pair interactions of a quadratic function define a graph. If that
graph has two disjoint edges, their witnesses can be placed on one binary
four-dimensional restriction. A Boolean quadratic function on four
relevant binary variables saturates the influence bound. We use this
saturation to show that every coordinate outside the restriction is
irrelevant on the entire alphabet. If the graph has no disjoint edges,
an elementary graph argument reduces it to a star or a triangle. Boolean
range rules out independent nonconstant components, and the triangle
alternative involves only three coordinates. Fixing the center of the
star leaves an additive Boolean function, hence a one-junta.

\section{Anchored expansions and interactions}\label{sec:interactions}

The arguments in this section apply to a product
$\Omega=\prod_{i=1}^n A_i$ of finite nonempty alphabets. Choose an anchor
$o\in\Omega$. For $x\in\Omega$ and $S\subseteq[n]$, write $o[S\leftarrow x]$
for the tuple agreeing with $x$ on $S$ and with $o$ elsewhere. We also use
$x[i\leftarrow a]$ for a one-coordinate replacement.

\begin{lemma}[Anchored expansion]\label{lem:anchor}
If $f:\Omega\to\R$ has degree at most two, then
\begin{equation}\label{eq:anchor}
 f(x)=c+\sum_i u_i(x_i)+\sum_{i<j}v_{ij}(x_i,x_j),
\end{equation}
where
\begin{align*}
 c&=f(o),\\
 u_i(a)&=f(o[i\leftarrow a])-f(o),\\
 v_{ij}(a,b)&=f(o[i\leftarrow a,j\leftarrow b])
  -f(o[i\leftarrow a])-f(o[j\leftarrow b])+f(o).
\end{align*}
The function $u_i$ vanishes at $o_i$, and $v_{ij}$ vanishes when either
argument is its anchor symbol. Conversely, every function of the form
\eqref{eq:anchor} has degree at most two.
\end{lemma}

\begin{proof}
All operators in the displayed formula are linear in $f$. It therefore
suffices to check a summand depending on zero, one, or two coordinates.
For a constant only $c$ remains. For a unary summand, $c$ and its unary
correction reconstruct it. For a summand on $i,j$, these terms together
with $v_{ij}$ reconstruct the summand, and every other correction is zero.
The converse follows directly from Definition~\ref{def:degree}.
\end{proof}

For distinct $i,j$, symbols $a,a'\in A_i$, $b,b'\in A_j$, and a fixed
background in the other coordinates, define the mixed difference
\begin{align*}
 \Delta_{ij}f(a,a';b,b')={}&f(x[i\leftarrow a,j\leftarrow b])
 -f(x[i\leftarrow a',j\leftarrow b])\\
 &-f(x[i\leftarrow a,j\leftarrow b'])
 +f(x[i\leftarrow a',j\leftarrow b']).
\end{align*}
For a degree-two function this quantity is independent of the background:
in~\eqref{eq:anchor}, all terms except $v_{ij}$ cancel. Likewise, a
difference of two sections in one coordinate has degree at most one on
the remaining coordinates. Restrictions to subalphabets preserve degree.

\begin{definition}
The \emph{interaction graph} of $f$ has vertex set $[n]$ and an edge $ij$
when some mixed difference $\Delta_{ij}f$ is nonzero. Equivalently,
$v_{ij}$ is not identically zero. This graph is independent of the anchor.
\end{definition}

An interaction makes both of its endpoints relevant. Restricting to a
subalphabet can remove interactions or relevance. In the proof below,
every binary restriction is chosen to preserve specified nonzero witnesses.

\begin{lemma}[Independent additive parts]\label{lem:additive}
Suppose a Boolean function is a sum of real-valued functions on disjoint
sets of coordinates. At most one summand is nonconstant. In particular,
a Boolean function of degree at most one depends on at most one coordinate.
\end{lemma}

\begin{proof}
If two summands have values $a<a'$ and $b<b'$, respectively, independence
of their coordinates realizes, with all other summands fixed, the three
strictly ordered sums
$a+b<a'+b<a'+b'$. A Boolean function has only two possible values.
The last assertion follows from the unary version of~\eqref{eq:anchor}.
\end{proof}

Grouping~\eqref{eq:anchor} by connected components of the interaction graph
gives independent additive parts. A component containing an edge has a
nonconstant part, because its corresponding mixed difference is nonzero.
An isolated vertex is relevant precisely when its unary part is
nonconstant. Lemma~\ref{lem:additive} consequently implies the following.

\begin{corollary}\label{cor:component}
For a nonconstant Boolean function of degree at most two, all relevant
coordinates lie in a single connected component of its interaction graph.
An isolated relevant coordinate forces the entire function to be unary.
\end{corollary}

\section{Binary saturation and full-alphabet rigidity}\label{sec:rigidity}

We first recall the binary equality case needed for the argument. On
$\{-1,1\}^4$, use the uniform measure and the Fourier characters
$\chi_S(z)=\prod_{i\in S}z_i$. For a real-valued function $g$, write
$\widehat g(S)=\E[g\chi_S]$.

\begin{lemma}[Binary saturation]\label{lem:saturation}
Let $g:\{-1,1\}^4\to\{-1,1\}$ have degree at most two and depend on all
four coordinates. Then
\begin{equation}\label{eq:pure}
 g(z)=\sum_{|S|=2}\widehat g(S)\chi_S(z),
 \qquad \sum_{|S|=2}\widehat g(S)^2=1.
\end{equation}
For every $i\in[4]$,
\begin{equation}\label{eq:avoid}
 \sum_{\substack{|S|=2\\i\notin S}}\widehat g(S)^2=\frac12.
\end{equation}
In particular, among the other three coordinates there is a nonzero
quadratic coefficient.
\end{lemma}

\begin{proof}
For each $i$, the half-difference
\[
 D_i g=\frac{g|_{z_i=1}-g|_{z_i=-1}}2
\]
is a nonzero affine function of the other three bits and takes values in
$\{-1,0,1\}$. A nonzero affine function on a binary cube is nonzero on at
least half the inputs. Indeed, if a variable coefficient is nonzero, at
most one of the two points in each fiber of that variable is a zero; if
all variable coefficients vanish, the function is a nonzero constant.
It follows that $\Inf_i(g):=\E[(D_i g)^2]\geq1/2$.

Parseval's identity and the degree bound yield
\[
 2\leq\sum_{i=1}^4\Inf_i(g)
   =\sum_S |S|\widehat g(S)^2
   \leq 2\sum_S\widehat g(S)^2=2.
\]
Equality throughout forces the constant and linear coefficients to vanish,
and gives $\Inf_i(g)=1/2$ for every $i$. Subtracting the quadratic mass
containing $i$ from the total mass one proves~\eqref{eq:avoid}.
\end{proof}

\begin{lemma}[A binary restriction determines all outside coordinates]
\label{lem:rigidity}
Let $F:\prod_{i=1}^n A_i\to\{-1,1\}$ have degree at most two. Suppose
there is a set $I$ of four coordinates, two distinct chosen symbols in
each coordinate of $I$, and fixed values for the remaining coordinates,
such that the resulting binary restriction depends on all four coordinates.
Then $F$ depends only on the coordinates in $I$ on the full product.
\end{lemma}

\begin{proof}
Identify each chosen symbol pair with $\{-1,1\}$. For every assignment $t$
to the coordinates outside $I$, let $g_t$ be the resulting function on
the same four-dimensional binary cube. Let $g=g_{t_0}$ be the restriction
in the hypothesis. Every quadratic Fourier coefficient of $g_t$ is the
same as that of $g$: mixed differences inside $I$ are independent of all
outside coordinates. By Lemma~\ref{lem:saturation}, these shared
quadratic coefficients already have squared norm one. Since $g_t$ is
sign-valued, Parseval forces all of its remaining coefficients to vanish.
Thus
\begin{equation}\label{eq:cylinder}
 g_t=g\qquad\text{for every outside assignment }t.
\end{equation}

It remains to handle symbols of the coordinates in $I$ that are absent
from the chosen binary cube. Fix $j\notin I$ and any $a,b\in A_j$, and set
\[
 D(x)=\frac{F(x[j\leftarrow a])-F(x[j\leftarrow b])}{2},
\]
regarding $D$ as a function of all coordinates other than $j$. This
function has degree at most one and takes values in $\{-1,0,1\}$.
By~\eqref{eq:cylinder}, it vanishes whenever the coordinates in $I$ lie
in their chosen symbol pairs, for every assignment of the other coordinates.

Choose an anchor with chosen symbols on $I$. The unary anchored expansion
of $D$ therefore has zero constant term and zero unary terms outside $I$.
It has the form
\begin{equation}\label{eq:D}
 D(x)=\sum_{i\in I}r_i(x_i),
\end{equation}
where $r_i$ vanishes on both chosen symbols of coordinate $i$.
To see the vanishing of each term, vary only that coordinate from the
anchor and use the vanishing on the entire cylinder.

Fix $i\in I$ and an arbitrary symbol $s\in A_i$. On the slice $x_i=s$
with the other three coordinates of $I$ restricted to their chosen pairs,
equation~\eqref{eq:D} gives $D=r_i(s)$. If $r_i(s)\ne0$, then it is
$1$ or $-1$. Two signs with half-difference $1$, or with half-difference
$-1$, are forced to be the corresponding opposite constants. Hence both
$F|_{x_j=a,x_i=s}$ and $F|_{x_j=b,x_i=s}$ are constant on this three-cube.

On the other hand,~\eqref{eq:avoid} gives a nonzero quadratic coefficient
of $g$ involving two coordinates in $I\setminus\{i\}$. Its mixed
difference is unchanged when $x_i$ is replaced by $s$ or $x_j$ by $a$
or $b$. It is therefore nonzero in the supposedly constant slice, a
contradiction. This proves $r_i(s)=0$ for every $i\in I$ and every symbol
$s$. Equation~\eqref{eq:D} now gives $D\equiv0$ on the full product.

The coordinate $j$ and its symbols $a,b$ were arbitrary. Every coordinate
outside $I$ is consequently irrelevant. Changing such coordinates one at
a time shows that $F$ depends only on $I$.
\end{proof}

The use of the global unary expansion in~\eqref{eq:D} is essential: it
handles assignments in which several coordinates of $I$ simultaneously
take new symbols. Merely proving invariance on one selected binary cube
would not establish the conclusion.

\begin{corollary}[Disjoint interactions force four variables]
\label{cor:disjoint}
If the interaction graph of a Boolean degree-two function contains two
disjoint edges $ij$ and $k\ell$, the function depends only on
$\{i,j,k,\ell\}$.
\end{corollary}

\begin{proof}
Choose two symbols in each endpoint of $ij$ witnessing its nonzero
mixed difference, and do the same for $k\ell$. These choices involve
disjoint coordinates, so they define a single binary four-cube. Both
interactions remain nonzero on this cube, regardless of the outside
assignment. Thus all four coordinates are relevant there. Apply
Lemma~\ref{lem:rigidity} to $F=2f-1$.
\end{proof}

\section{The selector alternative and the upper bound}

\begin{lemma}[Intersecting edges]\label{lem:graph}
A simple graph in which every two edges intersect either has a vertex
incident with every edge, or has all of its edges supported on three
vertices. The empty graph is included in the second alternative.
\end{lemma}

\begin{proof}
With at most one edge the assertion is immediate. Otherwise take distinct
edges $ab$ and $ac$. If every edge contains $a$, the first alternative
holds. An edge avoiding $a$ must be $bc$. Any edge meeting all three of
$ab,ac,bc$ has both endpoints in $\{a,b,c\}$, proving the second alternative.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:selector}]
Suppose $|\rel(f)|>4$. By Corollary~\ref{cor:disjoint}, every two
interaction edges intersect. The graph cannot be empty, since otherwise
$f$ is additive and Lemma~\ref{lem:additive} makes it a one-junta.
By Corollary~\ref{cor:component}, all relevant coordinates belong to its
single nonconstant component. The alternative in which all edges are
supported on three vertices would therefore give at most three relevant
coordinates. Lemma~\ref{lem:graph} consequently provides a common endpoint
$i$ of all edges.

Fix any $a\in A$ at coordinate $i$. In~\eqref{eq:anchor}, each remaining
pair term contains $i$, so after this substitution it becomes unary.
The section is an additive Boolean function. Lemma~\ref{lem:additive}
shows that it depends on at most one of the remaining coordinates.
\end{proof}

\begin{proof}[Upper bound in Theorem~\ref{thm:exact}]
There is nothing to prove when $|\rel(f)|\leq4$. Otherwise take the
selector $i$ given by Theorem~\ref{thm:selector}. For each $a\in[q]$,
let $S_a\subseteq[n]\setminus\{i\}$ be a set of size at most one
supporting the section $f|_{x_i=a}$.

If a coordinate $j\ne i$ is relevant to $f$, its two witnessing inputs
have the same value $a$ in coordinate $i$. It is then relevant to that
section, so $j\in S_a$. Therefore
\[
 \rel(f)\subseteq\{i\}\cup\bigcup_{a\in[q]}S_a,
 \qquad |\rel(f)|\leq1+\sum_{a\in[q]}|S_a|\leq q+1.
\]
This also covers all small dimensions through the initial four-variable
alternative; constants and the zero-dimensional cube have no relevant
coordinates.
\end{proof}

\section{Matching examples}\label{sec:lower}

We include the known examples to establish attainment for every alphabet.

\paragraph{The addressor.}
Choose a nonconstant $b:[q]\to\{0,1\}$. On $q+1$ coordinates define
\begin{equation}\label{eq:addressor}
 f(s,y_1,\ldots,y_q)=b(y_s)
   =\sum_{a=1}^q\ind_{\{s=a\}}b(y_a).
\end{equation}
Each summand depends on only $s$ and $y_a$, so the degree is at most two.
Every $y_a$ is relevant by setting $s=a$. The selector is relevant because
$q\geq2$ and two leaf coordinates can be assigned different $b$-values.
Hence $R_{2,q}\geq q+1$. This is the degree-two addressor underlying the
general decision-tree lower construction in~\cite{Val26}.

\paragraph{The binary square.}
For signs $a,b,c,d$, the standard quadratic example
\begin{equation}\label{eq:square}
 G(a,b,c,d)=\frac{(a+b)c+(a-b)d}{2}
\end{equation}
is always sign-valued: if $a=b$ it equals $ac$, and if $a=-b$ it equals
$ad$. It is quadratic and all four coordinates are relevant. Indeed,
$c$ matters when $a=b$, $d$ matters when $a=-b$, $a$ matters when $c=d$,
and $b$ matters when $c=-d$. This is a form of the familiar four-variable
quadratic Boolean example; see~\cite{Filmus22}.

For any $q\geq2$, choose a surjection $\sigma:[q]\to\{-1,1\}$ and define
\[
 h(x_1,x_2,x_3,x_4)=
 \frac{G(\sigma(x_1),\sigma(x_2),\sigma(x_3),\sigma(x_4))+1}{2}.
\]
The function $h$ is Boolean, has degree at most two, and depends on all
four coordinates. No restriction on the sizes of the fibers of $\sigma$
is needed. Thus $R_{2,q}\geq4$. Together with~\eqref{eq:addressor} and
the upper bound, this proves Theorem~\ref{thm:exact}.

\section{Formal verification}\label{sec:formal}

The exact bound and selector theorem have been formalized in Lean~4.
The formal degree hypothesis is literally the finite-sum formulation in
Definition~\ref{def:degree}: the summands are real-valued and each has at
most two globally relevant coordinates. Boolean range is required of
$f$, not of the summands. The formal result includes arbitrary natural
dimensions, all integers $q\geq2$, and the matching lower examples.

The main declarations, in namespace \lean{QaryQuadratic}, are
\begin{center}
\begin{tabular}{@{}ll@{}}
\toprule
Declaration & Statement\\
\midrule
\lean{sharp_qary_quadratic} & Theorem~\ref{thm:exact}, including attainment\\
\lean{source_quadratic_selector} & Theorem~\ref{thm:selector}\\
\bottomrule
\end{tabular}
\end{center}

The formal proof uses the same interaction and rigidity mechanism as the
mathematical proof. For the binary step, it proves a finite saturation
lemma for a four-cube with two disjoint nonzero interactions. The eleven
Boolean entries at inputs of Hamming weight at most two determine the
remaining five entries by the degree-two identities. Ordinary kernel
reduction verifies the required evenness and balance conditions. The
interface to this finite lemma derives its hypotheses from an arbitrary
real degree-two Boolean function. It does not assume a table constraint
in the main theorem. This supplies the uniqueness consequence of binary
saturation used in the cylinder argument.

The rest of the development proves the passage to arbitrary alphabets
and dimensions, including arbitrary outside backgrounds, arbitrary new
symbols in the four selected coordinates, the interaction-graph
alternative, selector counting, and coordinate relabeling for the lower
examples. The formal graph argument uses the isolated-coordinate case of
Corollary~\ref{cor:component} in place of an explicit connected-component
decomposition. A separate formal equivalence with complex Fourier degree
is not claimed; the checked statement uses the finite-sum definition.

\paragraph{Versions and trust boundary.}
The verification uses Lean~4.27.0, with compiler commit
\begin{center}\lean{db93fe1608548721853390a10cd40580fe7d22ae},\end{center}
and mathlib commit
\begin{center}\lean{a3a10db0e9d66acbebf76c5e6a135066525ac900}.\end{center}
The source package submitted to arXiv contains the Lean sources and
verification records under \texttt{anc/lean/}; the Hexagon deposit contains
the manuscript only.
The artifact records the dependency manifest, source hashes, reproduction
scripts, successful full-build output, and transitive axiom reports. An
independent rebuild compiled all twelve local proof modules and the
umbrella module from source, excluding earlier local compiled artifacts.
The two main declarations depend only on
\lean{propext}, \lean{Classical.choice}, and \lean{Quot.sound}.
There are no admitted lemmas or additional mathematical axioms. The finite
auxiliary lemma uses kernel \lean{decide}, with no \lean{native_decide}
or external numerical certificate. These checks concern the formal
statements and proof objects; the mathematical exposition above is a
separate presentation of the argument.

\begin{thebibliography}{9}

\bibitem{Filmus22}
Yuval Filmus.
\newblock Quadratic Boolean functions on the cube.
\newblock Manuscript, 27 March 2022.
\newblock \url{https://yuvalfilmus.cs.technion.ac.il/Manuscripts/Degree2.pdf}.

\bibitem{MV20}
Ivan Mogilnykh and Alexandr Valyuzhenich.
\newblock Equitable 2-partitions of the Hamming graphs with the second eigenvalue.
\newblock \emph{Discrete Mathematics}, 343(11):112039, 2020.
\newblock \href{https://doi.org/10.1016/j.disc.2020.112039}{doi:10.1016/j.disc.2020.112039}.
\newblock Preprint: \href{https://arxiv.org/abs/1903.12333}{arXiv:1903.12333}.

\bibitem{Val24}
Alexandr Valyuzhenich.
\newblock An upper bound on the number of relevant variables for Boolean
functions on the Hamming graph.
\newblock \emph{Discrete Mathematics}, 349(2):114745, 2026.
\newblock \href{https://doi.org/10.1016/j.disc.2025.114745}{doi:10.1016/j.disc.2025.114745}.
\newblock Preprint: \href{https://arxiv.org/abs/2404.10418v1}{arXiv:2404.10418v1}, 2024.

\bibitem{Val26}
Alexandr Valyuzhenich.
\newblock An upper bound on the number of relevant variables in a bounded
degree Boolean function on the Hamming graph.
\newblock \href{https://arxiv.org/abs/2609.12540v1}{arXiv:2609.12540v1}, 2026.

\end{thebibliography}
\end{document}