In this note we characterize when non-classical polynomials are necessary in the inverse theorem for the Gowers $U^k$-norm. We give a brief deduction of the fact that a bounded function on $mathbb F_p^n$ with large $U^k$-norm must correlate with a cl
assical polynomial when $kleq p+1$. To the best of our knowledge, this result is new for $k=p+1$ (when $p>2$). We then prove that non-classical polynomials are necessary in the inverse theorem for the Gowers $U^k$-norm over $mathbb F_p^n$ for all $kgeq p+2$, completely characterizing when classical polynomials suffice.
The following combinatorial conjecture arises naturally from recent ergodic-theoretic work of Ackelsberg, Bergelson, and Best. Let $M_1$, $M_2$ be $ktimes k$ integer matrices, $G$ be a finite abelian group of order $N$, and $Asubseteq G^k$ with $|A|g
ealpha N^k$. If $M_1$, $M_2$, $M_1-M_2$, and $M_1+M_2$ are automorphisms of $G^k$, is it true that there exists a popular difference $d in G^ksetminus{0}$ such that [#{x in G^k: x, x+M_1d, x+M_2d, x+(M_1+M_2)d in A} ge (alpha^4-o(1))N^k.] We show that this conjecture is false in general, but holds for $G = mathbb{F}_p^n$ with $p$ an odd prime given the additional spectral condition that no pair of eigenvalues of $M_1M_2^{-1}$ (over $overline{mathbb{F}}_p$) are negatives of each other. In particular, the rotated squares pattern does not satisfy this eigenvalue condition, and we give a construction of a set of positive density in $(mathbb{F}_5^n)^2$ for which that pattern has no nonzero popular difference. This is in surprising contrast to three-point patterns, which we handle over all compact abelian groups and which do not require an additional spectral condition.
We study variants of Mastermind, a popular board game in which the objective is sequence reconstruction. In this two-player game, the so-called textit{codemaker} constructs a hidden sequence $H = (h_1, h_2, ldots, h_n)$ of colors selected from an alp
habet $mathcal{A} = {1,2,ldots, k}$ (textit{i.e.,} $h_iinmathcal{A}$ for all $iin{1,2,ldots, n}$). The game then proceeds in turns, each of which consists of two parts: in turn $t$, the second player (the textit{codebreaker}) first submits a query sequence $Q_t = (q_1, q_2, ldots, q_n)$ with $q_iin mathcal{A}$ for all $i$, and second receives feedback $Delta(Q_t, H)$, where $Delta$ is some agreed-upon function of distance between two sequences with $n$ components. The game terminates when $Q_t = H$, and the codebreaker seeks to end the game in as few turns as possible. Throughout we let $f(n,k)$ denote the smallest integer such that the codebreaker can determine any $H$ in $f(n,k)$ turns. We prove three main results: First, when $H$ is known to be a permutation of ${1,2,ldots, n}$, we prove that $f(n, n)ge n - loglog n$ for all sufficiently large $n$. Second, we show that Knuths Minimax algorithm identifies any $H$ in at most $nk$ queries. Third, when feedback is not received until all queries have been submitted, we show that $f(n,k)=Omega(nlog k)$.
