Bent Boolean functions extremal objects that maximally resist affine approximation are notoriously hard to construct for large numbers of variables. We propose a hybrid quantum-classical genetic algorithm (GA) that uses a quantum circuit to evaluate the Gowers $U_2$ norm as the evolutionary fitness function. Our central contribution is a complexity-theoretic separation: the quantum evaluation circuit requires only $3n$ qubits and $\bigO(n^2)$ two-qubit gates per function query, whereas the classical computation of the exact Gowers $U_2$ norm demands $\bigO(2^{2n})$ arithmetic operations an exponential overhead that renders it infeasible for $n \gtrsim 25$. We validate the framework on $n=6$ and $n=8$ variable systems. For $n=8$, our classical GA run extended to 1000 generations achieves best fitness $\Utwof = 0.250000$ \emph{exactly} the theoretical bent threshold $2^{-n/4}$ with average fitness $0.257267$, confirming that the Gowers $U_2$ norm is a superior fitness criterion over Walsh-Hadamard spectral flatness. Quantum-assisted evaluation faithfully reproduces the classical trajectory up to finite-sampling noise, and our complexity analysis demonstrates that for $n > 25$ the
Gowers norms have been a key component in the proofs of many breakthrough results in connection to the sum of digits function. Spiegelhofer has used them to show that the Thue-Morse sequence has level of distribution 1 and also that it is equidistributed along cubes. Recently Gowers norms have been used to study the sum of digits function of the Zeckendorf expansion of primes. In this paper we unify the treatments of Gowers norms and give Gowers norms type estimates for a large class of linearly recurrent numeration systems.
In this paper we develop Host--Kra and inverse Gowers theory for abelian groups of bounded exponent. We show that the Host--Kra factors $Z^{\leq k}(\mathrm{X})$ associated with actions of such groups admit extensions with the structure of \emph{polynomial towers}. This new notion is a system obtained as a finite iteration of abelian extensions of the trivial system by polynomial cocycles; crucially, the intermediate extensions in this system are not required to agree with the Host--Kra factors. We prove that all such extensions are Abramov (generalizing a recent result of Candela, González-Sánchez, and Szegedy), but not necessarily Weyl, and have the structure of k-step translational systems. Combining this structure theorem with a correspondence principle due to the first and third authors, we derive an inverse theorem for the Gowers norms on finite abelian groups of bounded exponent: large $U^{k+1}$-norm implies large correlation with a polynomial of degree $\le k$ (on the same group), even when the exponent is not square-free or is divisible by small primes. This resolves a conjecture of the first and third authors for such groups, and also answers a question of Candela, Gonzále
In a blogpost in 2009, Gowers raised a possible approach to Littlewood's conjecture in Diophantine approximation, leading to a question about the existence of sufficiently many points in the unit cube such that "hyperbolic distance" between any two of them is large. In this note we answer this question by an explicit construction. This shows that this approach to prove Littlewood's conjecture cannot work, unless some further refinements are added.
Orthogonality relations for cubes of characters in Gowers inner products $\langle \cdot \rangle_{d,l}$ lead to Parseval-type identities and isometries for suitably generalized Gowers uniformity norms $U^{d,l}$.
We propose a family of quantum algorithms for estimating Gowers uniformity norms $ U^k $ over finite abelian groups and demonstrate their applications to testing polynomial structure and counting arithmetic progressions. Building on recent work for estimating the $ U^2 $-norm over $ \mathbb{F}_2^n $, we generalize the construction to arbitrary finite fields and abelian groups for higher values of $ k $. Our algorithms prepare quantum states encoding finite differences and apply Fourier sampling to estimate uniformity norms, enabling efficient detection of structural correlations. As a key application, we show that for certain degrees $ d = 4, 5, 6 $ and under appropriate conditions on the underlying field, there exist quasipolynomial-time quantum algorithms that distinguish whether a bounded function $ f(x) $ is a degree-$ d $ phase polynomial or far from any such structure. These algorithms leverage recent inverse theorems for Gowers norms, together with amplitude estimation, to reveal higher-order algebraic correlations. We also develop a quantum method for estimating the number of 3-term arithmetic progressions in Boolean functions $ f : \mathbb{F}_p^n \to \{0,1\} $, based on es
The \emph{Gowers uniformity norms} $\|f\|_{U^k(G)}$ of a function $f: G \to \C$ on a finite additive group $G$, together with the slight variant $\|f\|_{U^k([N])}$ defined for functions on a discrete interval $[N] := \{1,...,N\}$, are of importance in the modern theory of counting additive patterns (such as arithmetic progressions) inside large sets. Closely related to these norms are the \emph{Gowers-Host-Kra seminorms} $\|f\|_{U^k(X)}$ of a measurable function $f: X \to \C$ on a measure-preserving system $X = (X, {\mathcal X}, μ, T)$. Much recent effort has been devoted to the question of obtaining necessary and sufficient conditions for these Gowers norms to have non-trivial size (e.g. at least $η$ for some small $η> 0$), leading in particular to the inverse conjecture for the Gowers norms, and to the Host-Kra classification of characteristic factors for the Gowers-Host-Kra seminorms. In this paper we investigate the near-extremal (or "property testing") version of this question, when the Gowers norm or Gowers-Host-Kra seminorm of a function is almost as large as it can be subject to an $L^\infty$ or $L^p$ bound on its magnitude. Our main results assert, roughly speaking, tha
If $A$, $B$, $C$ are subsets in a finite simple group of Lie type $G$ at least two of which are normal with $|A||B||C|$ relatively large, then we establish a stronger conclusion than $ABC = G$. This is related to a theorem of Gowers and is a generalization of a theorem of Larsen, Shalev, Tiep and the second author and Pyber.
We prove quasipolynomial bounds on the inverse theorem for the Gowers $U^{s+1}[N]$-norm. The proof is modeled after work of Green, Tao, and Ziegler and uses as a crucial input recent work of the first author regarding the equidistribution of nilsequences. In a companion paper, this result will be used to improve the bounds on Szemerédi's theorem.
We examine multidimensional polynomial progressions involving linearly independent polynomials in finite fields, proving power saving bounds for sets lacking such configurations. This jointly generalises earlier results of Peluse (for the single dimensional case) and the author (for distinct degree polynomials). In contrast to the cases studied in the aforementioned two papers, a usual PET induction argument does not give Gowers norm control over multidimensional progressions that involve polynomials of the same degrees. The main challenge is therefore to obtain Gowers norm control, and we accomplish this for all multidimensional polynomial progressions with pairwise independent polynomials. The key inputs are: (1) a quantitative version of a PET induction scheme developed in ergodic theory by Donoso, Koutsogiannis, Ferré-Moragues and Sun, (2) a quantitative concatenation result for Gowers box norms in arbitrary finite abelian groups, motivated by earlier results of Tao, Ziegler, Peluse and Prendiville; (3) an adaptation to combinatorics of the box norm smoothing technique, recently developed in the ergodic setting by the author and Frantzikinakis; and (4) a new version of the mult
This paper is the third part of the series "Spherical higher order Fourier analysis over finite fields", aiming to develop the higher order Fourier analysis method along spheres over finite fields, and to solve the geometric Ramsey conjecture in the finite field setting. In this paper, we prove an inverse theorem over finite field for spherical Gowers norms, i.e. a local Gowers norm supported on a sphere. We show that if the $(s+1)$-th spherical Gowers norm of a 1-bounded function $f\colon\mathbb{F}_{p}^{d}\to \mathbb{C}$ is at least $ε$ and if $d$ is sufficiently large depending only on $s$, then $f$ correlates on the sphere with a $p$-periodic $s$-step nilsequence, where the bounds for the complexity and correlation depend only on $d$ and $ε$. This result will be used in later parts of the series to prove the geometric Ramsey conjecture in the finite field setting.
We prove that every additive set $A$ with energy $E(A)\ge |A|^3/K$ has a subset $A'\subseteq A$ of size $|A'|\ge (1-\varepsilon)K^{-1/2}|A|$ such that $|A'-A'|\le O_\varepsilon(K^{4}|A'|)$. This is, essentially, the largest structured set one can get in the Balog-Szemerédi-Gowers theorem.
In this paper we investigate the uniform distribution properties of polynomials in many variables and bounded degree over a fixed finite field F of prime order. Our main result is that a polynomial P : F^n -> F is poorly-distributed only if P is determined by the values of a few polynomials of lower degree, in which case we say that P has small rank. We give several applications of this result, paying particular attention to consequences for the theory of the so-called Gowers norms. We establish an inverse result for the Gowers U^{d+1}-norm of functions of the form f(x)= e_F(P(x)), where P : F^n -> F is a polynomial of degree less than F, showing that this norm can only be large if f correlates with e_F(Q(x)) for some polynomial Q : F^n -> F of degree at most d. The requirement deg(P) < |F| cannot be dropped entirely. Indeed, we show the above claim fails in characteristic 2 when d = 3 and deg(P)=4, showing that the quartic symmetric polynomial S_4 in F_2^n has large Gowers U^4-norm but does not correlate strongly with any cubic polynomial. This shows that the theory of Gowers norms in low characteristic is not as simple as previously supposed. This counterexample has a
We prove quantitative bounds for the inverse theorem for Gowers uniformity norms $\mathsf{U}^5$ and $\mathsf{U}^6$ in $\mathbb{F}_2^n$. The proof starts from an earlier partial result of Gowers and the author which reduces the inverse problem to a study of algebraic properties of certain multilinear forms. The bulk of the work in this paper is a study of the relationship between the natural actions of $\operatorname{Sym}_4$ and $\operatorname{Sym}_5$ on the space of multilinear forms and the partition rank, using an algebraic version of regularity method. Along the way, we give a positive answer to a conjecture of Tidor about approximately symmetric multilinear forms in 5 variables, which is known to be false in the case of 4 variables. Finally, we discuss the possible generalization of the argument for $\mathsf{U}^k$ norms.
Gowers' FIN$_k$ theorem, also called Gowers' pigeonhole principle or Gowers' theorem, is a Ramsey-type theorem. It first occurred in the study of Banach space theory and is a natural generalization of Hindman's theorem. In this short note, we will show that Gowers' FIN$_k$ theorem does not follow from ACA$_0$.
Gowers introduced, for d\geq 1, the notion of dimension-d uniformity U^d(f) of a function f: G -> \C, where G is a finite abelian group and \C are the complex numbers. Roughly speaking, if U^d(f) is small, then f has certain "pseudorandomness" properties. We prove the following property of functions with large U^d(f). Write G=G_1 x >... x G_n as a product of groups. If a bounded balanced function f:G_1 x ... x G_n -> \C is such that U^{d} (f) > epsilon, then one of the coordinates of f has influence at least epsilon/2^{O(d)}. The Gowers inner product of a collection of functions is a related notion of pseudorandomness. We prove that if a collection of bounded functions has large Gowers inner product, and at least one function in the collection is balanced, then there is a variable that has high influence for at least four of the functions in the collection. Finally, we relate the acceptance probability of the "hypergraph long-code test" proposed by Samorodnitsky and Trevisan to the Gowers inner product of the functions being tested and we deduce applications to the construction of Probabilistically Checkable Proofs and to hardness of approximation.
Let $G$ be a finite-dimensional vector space over a prime field $\mathbb{F}_p$ with some subspaces $H_1, \dots, H_k$. Let $f \colon G \to \mathbb{C}$ be a function. Generalizing the notion of Gowers uniformity norms, Austin introduced directional Gowers uniformity norms of $f$ over $(H_1, \dots, H_k)$ as \[\|f\|_{\mathsf{U}(H_1, \dots, H_k)}^{2^k} = \mathbb{E}_{x \in G,h_1 \in H_1, \dots, h_k \in H_k} \partial_{h_1} \dots \partial_{h_k} f(x)\] where $\partial_u f(x) \colon= f(x + u) \overline{f(x)}$ is the discrete multiplicative derivative. Suppose that $G$ is a direct sum of subspaces $G = U_1 \oplus U_2 \oplus \dots \oplus U_k$. In this paper we prove the inverse theorem for the norm \[\|\cdot\|_{\mathsf{U}(U_1, \dots, U_k, \smash[b]{\underbrace{\scriptstyle G, \dots, G}_{\scriptscriptstyle \ell}})},\] which is the simplest interesting unknown case of the inverse problem for the directional Gowers uniformity norms. Namely, writing $\|\cdot\|_{\mathsf{U}}$ for the norm above, we show that if $f \colon G \to \mathbb{C}$ is a function bounded by 1 in magnitude and obeying $\|f\|_{\mathsf{U}} \geq c$, provided $\ell < p$, one can find a polynomial $α\colon G \to \mathbb{F}_p$ of
We establish a number of "concatenation theorems" that assert, roughly speaking, that if a function exhibits "polynomial" (or "Gowers anti-uniform", "uniformly almost periodic", or "nilsequence") behaviour in two different directions separately, then it also exhibits the same behavior (but at higher degree) in both directions jointly. Among other things, this allows one to control averaged local Gowers uniformity norms by global Gowers uniformity norms. In a sequel to this paper, we will apply such control to obtain asymptotics for "polynomial progressions" $n+P_1(r),\dots,n+P_k(r)$ in various sets of integers, such as the prime numbers.
A central tool in the study of systems of linear equations with integer coefficients is the Generalised von Neumann Theorem of Green and Tao. This theorem reduces the task of counting the weighted solutions of these equations to that of counting the weighted solutions for a particular family of forms, the Gowers norms $\Vert f \Vert_{U^{s+1}[N]}$ of the weight $f$. In this paper we consider systems of linear inequalities with real coefficients, and show that the number of solutions to such weighted diophantine inequalities may also be bounded by Gowers norms. Furthermore, we provide a necessary and sufficient condition for a system of real linear forms to be governed by Gowers norms in this way. We present applications to cancellation of the Möbius function over certain sequences. The machinery developed in this paper can be adapted to the case in which the weights are unbounded but suitably pseudorandom, with applications to counting the number of solutions to diophantine inequalities over the primes. Substantial extra difficulties occur in this setting, however, and we have prepared a separate paper on these issues.
Let $p$ be a fixed prime number, and $N$ be a large integer. The 'Inverse Conjecture for the Gowers norm' states that if the "$d$-th Gowers norm" of a function $f:\F_p^N \to \F_p$ is non-negligible, that is larger than a constant independent of $N$, then $f$ can be non-trivially approximated by a degree $d-1$ polynomial. The conjecture is known to hold for $d=2,3$ and for any prime $p$. In this paper we show the conjecture to be false for $p=2$ and for $d = 4$, by presenting an explicit function whose 4-th Gowers norm is non-negligible, but whose correlation any polynomial of degree 3 is exponentially small. Essentially the same result (with different correlation bounds) was independently obtained by Green and Tao \cite{gt07}. Their analysis uses a modification of a Ramsey-type argument of Alon and Beigel \cite{ab} to show inapproximability of certain functions by low-degree polynomials. We observe that a combination of our results with the argument of Alon and Beigel implies the inverse conjecture to be false for any prime $p$, for $d = p^2$.