\documentclass[11pt]{article} \usepackage[T1]{fontenc} \usepackage[utf8]{inputenc} \usepackage{lmodern} \usepackage[margin=1in]{geometry} \usepackage{amsmath,amssymb,amsthm,mathtools} \usepackage{microtype} \usepackage{xcolor} \usepackage{booktabs,array} \usepackage{enumitem} \usepackage{xurl} \usepackage[colorlinks=true,linkcolor=blue!55!black,citecolor=blue!55!black,urlcolor=blue!55!black]{hyperref} \hypersetup{pdftitle={A Polynomial Separation for Adaptive Fourier-Overlap Parity Decision Trees},pdfauthor={Yuran Xiu}} \setlength{\emergencystretch}{2em} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newcommand{\F}{\mathbb F} \newcommand{\R}{\mathbb R} \newcommand{\supp}{\operatorname{supp}} \newcommand{\PDT}{\operatorname{PDT}} \newcommand{\ind}{\mathbf 1} \newcommand{\wt}{\widehat} \newcommand{\code}[1]{\texttt{\detokenize{#1}}} \newcommand{\artifactroot}{\path{research/three-more-tcs-2026-10-14/02-adaptive-parity/}} \title{A Polynomial Separation for Adaptive Fourier-Overlap\protect\\ Parity Decision Trees} \author{Yuran Xiu\\ Institute for Interdisciplinary Information Sciences\\ Tsinghua University\\ \texttt{xiuyr23@mails.tsinghua.edu.cn}} \date{October 15, 2026} \begin{document} \maketitle \begin{abstract} Consider the parity decision tree rule that, at every nonconstant restriction, queries a nonzero character maximizing the intersection of the current Fourier support with its translate. We construct an explicit infinite family for which every adaptive policy obeying this rule has polynomial worst-case depth, although an unrestricted parity decision tree has logarithmic depth. For every $\ell\geq1$, let $R=2^\ell$. Our function has $n=4\ell-1+R^2\ell+R$ input bits and exactly $k=R^6-R^5+R$ nonzero Fourier coefficients. Every history-dependent maximizing policy terminates and computes the function, but has a feasible path of length at least $R>k^{1/6}$; an explicit unrestricted tree has depth at most $5\ell\leq\log_2 k$. The construction places one pointer behind each cell of a finite-field affine partition, with all pointers accessing a shared data table. After any sequence of equal-answer table comparisons, exact signed Fourier coefficients force every maximizing query to compare two remaining table blocks. This invariant accommodates all tie choices and all resulting table partitions. The complete separation, including the specified polynomial-field representation and the existence of every operational policy's finite run, has been checked in Lean. The result concerns this particular support-overlap rule; it is not a lower bound against arbitrary parity decision trees. \end{abstract} \section{Introduction} A parity decision tree may query the parity of any subset of the input bits. One approach to constructing shallow trees for a Fourier-sparse Boolean function is to fold many supported characters together at each query. If $S$ is the current Fourier support, the number of ordered endpoints that fold in direction $\gamma\neq0$ is \[ C_S(\gamma)=|S\cap(S+\gamma)|. \] Choosing a direction with maximum $C_S(\gamma)$ is a natural local rule. Its behavior is inherently adaptive: after an answer, coefficients combine with signs, some sums vanish, and the next score must be evaluated on the resulting function. A bound on the initial support alone does not control that process. We give a separation that survives this adaptivity. Every maximizing choice, including any dependence on the entire preceding query-answer history, has a long feasible branch. At the same time, reading an address and then a pointer computes the same function with few queries. \begin{theorem}[Main result]\label{thm:main} For every integer $\ell\geq1$, put $R=2^\ell$ and $n=4\ell-1+R^2\ell+R$. There is an explicitly specified function $f_\ell:\F_2^n\to\{-1,1\}$ with Fourier sparsity \begin{equation}\label{eq:main-k} k_\ell=R^6-R^5+R \end{equation} such that the following statements hold. \begin{enumerate}[label=\textup{(\roman*)},leftmargin=*] \item Every policy that queries an intrinsically nonzero character of maximum current support-overlap at each nonconstant restriction has a unique finite decision tree run, which computes $f_\ell$. \item For every such policy, that tree has a feasible path of length at least $R>k_\ell^{1/6}$. The bound permits every history-dependent tie rule and every choice of affine coordinates on the current domain. \item An explicit unrestricted parity decision tree computes $f_\ell$ with depth at most $5\ell\leq\log_2 k_\ell$. \end{enumerate} Furthermore, $k_\ell\to\infty$ as $\ell\to\infty$. \end{theorem} The adjective ``intrinsically'' excludes a parity that is constant on the current affine domain, even if its ambient coefficient vector is nonzero. The precise operational rule is defined in Section~\ref{sec:rule}. In particular, the algorithm stops exactly when the restricted function is constant. A singleton Fourier support need not be constant, so it is not an alternative stopping condition. \paragraph{Relation to earlier work.} Tsang, Wong, Xie, and Zhang~\cite{TWXZ13} study Fourier sparsity and spectral norm in parity decision tree constructions. Their coefficient-based methods should be distinguished from the support-cardinality maximization rule analyzed here. Mande and Sanyal~\cite{MS20} develop a folding approach and formulate a structural conjecture about the abundance of folding pairs. Hatami, Hosseini, Lovett, and Ostuni~\cite{HHLO24} refute two proposed additive structure conjectures. Their Theorem~8 bounds intersections of translates of the initial support of a constructed function; that statement itself does not quantify over the current supports along every adaptive execution. Tarannikov~\cite{Tar26} constructs a stronger initial-support example using an affine partition obtained from a linear spread. Section~4 of that work separates an inheritance assumption under restrictions from an adaptive depth claim. We use the finite-field spread geometry behind that partition, and give its required properties explicitly below. Addressing and table indirection are standard construction ideas. The contribution here is their composition with a shared table and the exact current-spectrum argument that forces comparisons after every possible sequence of table merges. We make no claim that the affine partition or the elementary Fourier identities are new. The theorem is a limitation of the specified maximum-overlap rule. It neither refutes the XOR log-rank conjecture nor establishes a limitation of all algorithms described as greedy. \paragraph{Proof mechanism.} The address selects one of $N=R^2$ cells. Each cell has an independent $\ell$-bit pointer, and the selected pointer addresses a common table of $R$ data bits. Along a branch that always answers a comparison by equality, the current table is described by an arbitrary partition into $r$ blocks. We compute the signed Fourier coefficients for every such partition. The finite-field geometry bounds every query with a nonzero address or pointer component. Meanwhile, the fact that the block indicators sum to one forces some pair of their nonconstant Fourier supports to overlap substantially. That pair gives a strictly better table-comparison score. Thus all maximizers are comparisons, equality merges the chosen pair, and the argument repeats until only one nonconstant data bit remains. \section{Fourier conventions and the operational rule}\label{sec:rule} For a finite-dimensional binary vector space $V$, let $V^*$ denote its dual. For $\alpha\in V^*$, write $\chi_\alpha(x)=(-1)^{\alpha(x)}$. The normalized Fourier transform of $g:V\to\R$ is \[ \wt g(\alpha)=\frac1{|V|}\sum_{x\in V}g(x)\chi_\alpha(x),\qquad S(g)=\{\alpha\in V^*: \wt g(\alpha)\neq0\}. \] The zero character belongs to $S(g)$ exactly when its coefficient is nonzero. Character orthogonality gives Fourier inversion $g=\sum_\alpha\wt g(\alpha)\chi_\alpha$. Indeed, a nonzero character sums to zero by pairing $x$ with $x+x_0$ for any $x_0$ at which that character is $-1$. Applying this identity to the difference of two characters yields the orthogonality formula and inversion. For $\gamma\in V^*$ define \begin{equation}\label{eq:score} C_g(\gamma)=|S(g)\cap(S(g)+\gamma)|. \end{equation} For $\gamma\neq0$, this is twice the number of unordered supported pairs whose sum is $\gamma$. Thus the ordered-endpoint and unordered-pair conventions give exactly the same maximizing queries. A current domain is a nonempty affine subspace $D$ of the original input space. Choose an affine bijection $\phi:V\to D$, and put $g=f\circ\phi$. Every ambient parity restricted to $D$ has the form $\gamma(x)+c$ in this chart. It is \emph{intrinsically nonzero} if $\gamma\neq0$. The constant $c$ changes the names of its two answers, but not its score. \begin{lemma}[Coordinate invariance]\label{lem:chart} The maximum-overlap rule is independent of the affine chart. Every intrinsic character is the linear part of an ambient parity restricted to $D$. \end{lemma} \begin{proof} Two charts differ by $x=By+t$, where $B$ is an invertible linear map. If $h(y)=g(By+t)$, then a change of variables gives \[ \wt h(B^*\alpha)=(-1)^{\alpha(t)}\wt g(\alpha), \] where $B^*\alpha=\alpha\circ B$. Hence $S(h)=B^*S(g)$ and $C_h(B^*\gamma)=C_g(\gamma)$. This is a bijection between nonzero characters and preserves all ties. Finally, a linear functional on the direction space of $D$ extends to the ambient space by extending a basis and assigning arbitrary values on the added basis vectors. Its value on the translation of $D$ contributes only the constant $c$. \end{proof} \begin{definition}[Maximizing policy]\label{def:policy} A maximizing policy assigns, to every finite history of ambient queries and answers and every nonempty current affine domain on which $f$ is nonconstant, an ambient parity whose intrinsic character is nonzero and maximizes \eqref{eq:score} for the actual current restriction. Its run outputs the constant value at a constant domain; otherwise it makes the assigned query and continues on each answer domain with the extended history. \end{definition} The score in this definition uses the support of the actual restricted function, after adding coefficients and performing all cancellations. The policy may use the entire history to choose among ties. No fixed order of maximizing directions is imposed. \begin{lemma}[Existence, termination, and uniqueness]\label{lem:termination} For every Boolean function on a finite binary cube, maximizing policies exist. Every such policy has a unique finite run from any nonempty affine domain. The run computes the restricted function and has depth strictly less than the cardinality of that domain. \end{lemma} \begin{proof} At a nonconstant domain, a chart has at least two points, so its dual has a nonzero character. The finite nonempty set of nonzero characters has a maximum score. Lemma~\ref{lem:chart} extends any maximizer to an ambient query, so policies can be defined at every required state. For an intrinsically nonzero query $\gamma$, choose $x_0$ with $\gamma(x_0)=1$. Translation by $x_0$ interchanges the two intrinsic answer fibers. Both fibers are therefore nonempty proper affine subspaces. This remains true after any answer-label shift. Their cardinalities are strictly smaller than that of the current domain. Strong induction on domain cardinality now constructs the run. A constant domain gives its uniquely determined constant leaf. At a nonconstant domain, the policy specifies a single query and induction constructs both subtrees. If the child domains have sizes $d_0,d_10$. If $r\geq2$, then $p_j\geq1$ for every $j$. For every $\beta\neq0$, the number $d_\beta=|\{j:\beta\in P_j\}|$ is either zero or at least two. \end{lemma} \begin{proof} The formula at zero is immediate. If $r\geq2$, each $B_j$ is nonempty and proper. If its nonconstant coefficients all vanished, Fourier inversion would make $\ind_{B_j}$ a constant function, a contradiction. The partition identity $\sum_j\ind_{B_j}=1$ implies $\sum_jb_j(\beta)=0$ for every nonzero $\beta$. Exactly one nonzero summand cannot have sum zero, proving the last assertion. \end{proof} Let \[ U=X_0^*\oplus\bigoplus_{i\in K}B^* \] be the frequency space of the address and pointers. Write $E_i\beta$ for the pointer frequency with entry $\beta$ in block $i$ and zero elsewhere. Let $e_j$ be the $j$th standard basis character on the current data bits. \begin{lemma}[Current signed spectrum]\label{lem:spectrum} The support of $H_j$ is exactly the disjoint union \begin{equation}\label{eq:Tj} T_j=\{0\}\;\dot\cup\; \{(a,E_i\beta):i\in K,\ a\in L_i,\ \beta\in P_j\}. \end{equation} Its coefficient at $0$ is $b_j(0)$, and its coefficient at $(a,E_i\beta)$ in the second set is $N^{-1}\varepsilon_i(a)b_j(\beta)$. Consequently, \begin{equation}\label{eq:S-grouped} S(F_{\mathcal B})=\mathop{\dot\bigcup}_{j=1}^r(T_j\times\{e_j\}), \qquad |T_j|=1+N^2p_j. \end{equation} \end{lemma} \begin{proof} Expand $\ind_{B_j}(Y_i)$ in its pointer Fourier basis. Its zero-frequency term is the same $b_j(0)$ for every $i$, so all zero-pointer contributions to $H_j$ sum to \[ b_j(0)\sum_{i\in K}\ind_{\mathcal A_i}(x)=b_j(0). \] This cancels every nonzero pure address coefficient arising from those terms and leaves only the origin. For a nonzero pointer frequency $\beta$, the term involving pointer $i$ has frequency $(a,E_i\beta)$ and coefficient $N^{-1}\varepsilon_i(a)b_j(\beta)$ by Lemma~\ref{lem:cell-fourier}. Different pairs $(i,\beta)$ with $\beta\neq0$ yield different pointer frequencies: a nonzero frequency in one block cannot equal a frequency in another block. Thus there are no further additions between these terms. The coefficient is nonzero exactly when $a\in L_i$ and $\beta\in P_j$. This proves \eqref{eq:Tj} with the stated signs. Each $i$ contributes $Np_j$ elements, and there are $N$ indices $i$, giving $|T_j|=1+N^2p_j$. Multiplication by $(-1)^{v_j}$ places the entire spectrum of $H_j$ in data layer $e_j$. These data characters are distinct, so different layers cannot cancel. This proves \eqref{eq:S-grouped}. \end{proof} The origin in $T_j$ is an \emph{inner} frequency. Its full frequency in $F_{\mathcal B}$ is $(0,e_j)$, which is nonzero. This distinction will supply the strict advantage in the comparison score. \begin{corollary}[Initial sparsity]\label{cor:sparsity} The function $f_\ell$ has exactly $R(1+N^2(R-1))=R^6-R^5+R$ nonzero Fourier coefficients. \end{corollary} \begin{proof} Initially the blocks are singletons. For a singleton $\{s\}$, $b_j(\beta)=R^{-1}(-1)^{\beta(s)}$ is nonzero for every $\beta$, so $p_j=R-1$. Sum \eqref{eq:S-grouped} over the $R$ data layers and use $N=R^2$. \end{proof} \section{Strict dominance of table comparisons}\label{sec:dominance} All scores in this section concern the actual current function $F_{\mathcal B}$. For subsets $Q,T\subseteq B^*\setminus\{0\}$, define \[ \mathcal T_Q=\{0\}\;\dot\cup\; \{(a,E_i\beta):i\in K,\ a\in L_i,\ \beta\in Q\}. \] For $z\in U$, write \[ I(Q,T;z)=|\mathcal T_Q\cap(\mathcal T_T+z)| =|\{u\in\mathcal T_Q:u+z\in\mathcal T_T\}|. \] Translation by $z$ is a bijection between the two orientations, so $I(Q,T;z)=I(T,Q;z)$. \begin{lemma}[All nonzero inner shifts]\label{lem:cross} For every $z\neq0$ in $U$, \begin{equation}\label{eq:cross} I(Q,T;z)\leq N(|Q|+|T|). \end{equation} For a nonzero pure address shift $z=(a,0)$, more precisely, \begin{equation}\label{eq:address-cross} I(Q,T;(a,0))=N|Q\cap T|\,|\{i:a\in L_i\}| \leq2N|Q\cap T|. \end{equation} \end{lemma} \begin{proof} First suppose $z=(a,\eta)$ has $\eta\neq0$. Choose a pointer coordinate $(i,t)$ at which $\eta$ is one. If $u\in\mathcal T_Q$ and $u+z\in\mathcal T_T$, at least one of these two endpoints has coordinate $(i,t)$ equal to one. Every member of $\mathcal T_Q$ with that coordinate one is in pointer block $i$, and there are at most $N|Q|$ such members. Likewise, at most $N|T|$ members of $\mathcal T_T$ have that coordinate one. The collision set is contained in the union of the first set and the translate by $z$ of the second set, proving \eqref{eq:cross}. This cover includes the origin whenever it is an endpoint: the other endpoint then has the chosen coordinate equal to one. The argument permits any address component and any number of nonzero pointer blocks. It remains to consider $z=(a,0)$ with $a\neq0$. The origin cannot be an endpoint of a collision, because the only zero-pointer element of either layer is the origin. Both endpoints therefore have the same nonzero pointer frequency, forcing a common block $i$ and a common $\beta\in Q\cap T$. Their address frequencies lie in $L_i\cap(L_i+a)$, which is $L_i$ if $a\in L_i$ and empty otherwise. Counting gives the equality in \eqref{eq:address-cross}. The incidence bound in Lemma~\ref{lem:geometry} gives its inequality. Finally, $2|Q\cap T|\leq|Q|+|T|$, proving \eqref{eq:cross} also in this case. \end{proof} \begin{lemma}[Exhaustive data-layer scores]\label{lem:layer-score} Write a query frequency as $(z,d)$, with $z\in U$ and $d\in(\F_2^r)^*$. Then \begin{align} C_{F_{\mathcal B}}(z,0) &=\sum_{j=1}^r I(P_j,P_j;z),\label{eq:inner-score}\\ C_{F_{\mathcal B}}(z,e_j+e_h) &=2I(P_j,P_h;z)\quad(j\neq h),\label{eq:mixed-score}\\ C_{F_{\mathcal B}}(z,d)&=0 \quad\bigl(d\notin\{0\}\cup\{e_j+e_h:j\neq h\}\bigr). \label{eq:other-score} \end{align} \end{lemma} \begin{proof} By \eqref{eq:S-grouped}, the supported data characters are exactly the $e_j$. A collision from layer $e_j$ to layer $e_h$ requires $d=e_j+e_h$. If $d=0$, this forces $j=h$, giving \eqref{eq:inner-score}. If $d\neq0$, it must have ones at exactly two distinct coordinates $j,h$. Only the orientations $(j,h)$ and $(h,j)$ are then possible. They have equal cardinalities by translation, proving \eqref{eq:mixed-score}. All other $d$ give no collisions. \end{proof} \begin{proposition}[Uniform bound away from pure comparisons]\label{prop:bound} For every query with nonzero inner part $z$, \begin{equation}\label{eq:bound} C_{F_{\mathcal B}}(z,d)\leq 2NP. \end{equation} For $z=0$ and $d$ neither zero nor a sum of two distinct data characters, the score is zero. \end{proposition} \begin{proof} For $d=0$, Lemmas~\ref{lem:cross} and \ref{lem:layer-score} give $\sum_j N(2p_j)=2NP$. For $d=e_j+e_h$ with $j\neq h$, they give $2N(p_j+p_h)\leq2NP$. Every remaining nonzero data component has zero score by \eqref{eq:other-score}. That same formula proves the final assertion when $z=0$. These cases exhaust all characters except the excluded zero query and the pure comparisons $(0,e_j+e_h)$. \end{proof} \begin{lemma}[A strictly better pure comparison]\label{lem:strict} If $2\leq r\leq R$, there are distinct $j,h$ with \begin{equation}\label{eq:strict} C_{F_{\mathcal B}}(0,e_j+e_h)>2NP. \end{equation} \end{lemma} \begin{proof} The zero inner shift gives \begin{equation}\label{eq:comparison-score} C_{F_{\mathcal B}}(0,e_j+e_h) =2\bigl(1+N^2|P_j\cap P_h|\bigr). \end{equation} Indeed, $\mathcal T_{P_j}\cap\mathcal T_{P_h}$ contains the origin, and for each of the $N$ pointer blocks it contains $N$ address frequencies for each $\beta\in P_j\cap P_h$. The factor two is the two orientations in \eqref{eq:mixed-score}. Double-counting the common nonzero pointer frequencies yields \[ \sum_{j0$, its score is at least \[ 2+\frac{2N^2P}{r(r-1)}\geq 2+2NP>2NP. \] The contribution of the common inner origin gives the strict inequality. \end{proof} \begin{theorem}[All-partition dominance]\label{thm:dominance} For every partition $\mathcal B$ of $B$ into $2\leq r\leq R$ nonempty blocks, every maximizing nonzero character for the current function $F_{\mathcal B}$ is exactly \[ (0,e_j+e_h)\qquad\text{for some distinct }j,h. \] \end{theorem} \begin{proof} Lemma~\ref{lem:strict} supplies a query whose score is strictly larger than $2NP$. Proposition~\ref{prop:bound} bounds every nonzero character outside the displayed set by $2NP$. No such character can maximize. The strictness also excludes ties between a comparison and any mixed, address, pointer, or other data query. Ties among the pure comparisons are unrestricted. \end{proof} This theorem holds for every table partition. It does not assert that the spread geometry survives every restriction of the address variables. The branch used next leaves those variables free, which is exactly the condition under which the displayed current-function formulas apply. \section{Every adaptive policy has a long feasible branch}\label{sec:lower} \begin{lemma}[Exact equality restriction]\label{lem:merge} If the current partition is $\mathcal B$ and the query is $v_j+v_h$, the answer zero produces $F_{\mathcal B'}$, where $\mathcal B'$ replaces $B_j,B_h$ by their union and retains all other blocks. \end{lemma} \begin{proof} The answer says $v_j=v_h$. In \eqref{eq:grouped}, their two terms become $(H_j+H_h)(-1)^{v_j}$. Since the blocks are disjoint, $\ind_{B_j}+\ind_{B_h}=\ind_{B_j\cup B_h}$, so $H_j+H_h$ is exactly the layer associated to the union block. All other terms are unchanged. The union's pointer coefficient is $b_j(\beta)+b_h(\beta)$, which may vanish. Its new set of nonzero frequencies is computed from this sum, as in \eqref{eq:block-coeff}. No projected or uncancelled old support is substituted for the new one. \end{proof} \begin{proposition}[Long zero-table paths]\label{prop:long} For every maximizing policy for $f_\ell$ and every fixed choice of address and pointer bits, the run on the input with those inner bits and with $w_s=0$ for all $s\in B$ has length at least $R$. \end{proposition} \begin{proof} Its finite run exists by Lemma~\ref{lem:termination}. Initially the current table partition has $R$ singleton blocks. Suppose that $r\geq2$ blocks remain along the specified input's path. In the canonical current chart, Theorem~\ref{thm:dominance} forces the policy's query to have intrinsic character $v_j+v_h$ for some distinct blocks, regardless of the history or tie choices. The all-zero table satisfies the equality answer. By Lemma~\ref{lem:merge}, the new domain is precisely that for the partition with these two blocks merged. Address and pointer variables remain free, and the number of independent data bits decreases by exactly one. The domain cannot be a constant leaf at any such stage. For example, setting every free data bit to zero makes the function $+1$ everywhere in the inner variables, whereas setting every free data bit to one makes it $-1$. Both assignments obey the current equality constraints. Thus the induction continues for $R-1$ comparisons. After these comparisons the partition has one block, namely $B$. Formula \eqref{eq:grouped} becomes $F_{\mathcal B}=(-1)^{v_1}$, because its sole inner layer is identically one. This is still nonconstant, so at least one additional query is required before the run can reach a constant leaf. The total length is at least $R$. To check chart freedom, an arbitrary chart may express the same restricted ambient query as $v_j+v_h+c$. The specified input then follows answer $c$, which imposes the same equality. Lemma~\ref{lem:chart} preserves all maximizers under the coordinate change. In the canonical chart the current domain consists solely of homogeneous table equalities and contains the ambient zero input. An ambient linear parity with intrinsic form $v_j+v_h$ therefore has no constant offset there; any offset in another chart merely relabels answers. Hence the branch is a branch of the actual policy run and is realized by the fixed original input. This also explains why an adaptive choice of chart cannot circumvent the induction. \end{proof} \begin{proof}[Proof of Theorem~\ref{thm:main}] The function is the explicitly specified Boolean function \eqref{eq:function}; its dimension and short tree are given in Section~\ref{sec:function}. Corollary~\ref{cor:sparsity} gives its exact sparsity. Lemma~\ref{lem:termination} applies to every policy and proves existence, uniqueness, termination, and correctness of its run. Proposition~\ref{prop:long} gives the $R$ lower bound on a feasible path of every such run. It remains to check the numerical comparison. For $R\geq2$, \[ k_\ell-R^5=R^5(R-2)+R\geq0, \qquad R^6-k_\ell=R^5-R>0. \] Thus \[ R^5\leq k_\ell