Second moments of pattern counts in dual Melas codewords

Statement

Let $k \geq3$, $F = \mathbb{F}_{2^k}$, $n = 2^k-1$, $\chi(z)=(-1)^{\operatorname{Tr}(z)}$ where $\operatorname{Tr}=\operatorname{Tr}_{F/\mathbb{F}_2}$, and let $\alpha\in F$ be primitive. For $c \in F^{*}$ put $S_c(i)=\operatorname{Tr}(\alpha^i+c\alpha^{-i})$, $i \in\mathbb{Z}/n$. As in [5], for $w \in\mathbb{F}_2^k$ let $N_w$ be the number of $i \in\mathbb{Z}/n$ with $(S_c(i),\ldots,S_c(i+k-1))=w$ (indices mod $n$), let $X_{k,c}(w)=N_w$ on $\mathbb{F}_2^k$ with the uniform measure, and

For $N\geq2$ let $\tau_N$ denote the maximal number of monic divisors of a nonzero polynomial of degree $\leq N$ in $\mathbb{F}_2[s]$.

Conjecture 35 of [5] asserts convergence in distribution to $\mathcal{P}(1)$, and [5] proposes to prove it through the convergence of all factorial moments; Theorem 1 establishes the second of these steps uniformly in $c$. Compare [5 Theorem 37], which gives $\limsup_k M_2^{(k,c_k)}\leq2$ for every sequence and $M_2^{(k,c_k)}\to1$ for almost every sequence. Since $M_1^{(k,c)}=1-2^{-k}$, Theorem 1 also gives $\operatorname{Var}(X_{k,c})\to1$ uniformly in $c$. The exponent $1/22$ is not optimised.

Throughout, $P_\ell\subset\mathbb{F}_2[x]$ (or $\mathbb{F}_2[s]$) denotes the set of polynomials of degree $<\ell$ (including 0).

Zero windows and the norm $h(\alpha)h(\alpha^{-1})$

Let $m_{\alpha}$, $m_{\alpha^{-1}}$ be the minimal polynomials of $\alpha,\alpha^{-1}$ over $\mathbb{F}_2$. They are distinct: otherwise $\alpha^{-1}=\alpha^{2^j}$ with $0\le j<k$, so $n\mid2^j+1\le2^{k-1}+1<n$. Put $M=m_{\alpha}m_{\alpha^{-1}}$ (degree $2k$), $R=\mathbb{F}_2[x]/(M)$, and identify $R\cong F\times F$ by $h\mapsto(h(\alpha),h(\alpha^{-1}))$. For $h\in R$ put $\operatorname{Nm}(h)=h(\alpha)h(\alpha^{-1})\in F$. Every $h\in P_k\setminus\{0\}$ satisfies $h(\alpha)\ne0\ne h(\alpha^{-1})$, since $\deg h<k$.

Proof. Let $\tau:R\to\mathbb{F}_2$ send $z$ to the coefficient of $x^{2k-1}$ of its representative of degree $<2k$. The pairing $(z,w)\mapsto\tau(zw)$ is nondegenerate: on the basis $x^0,\ldots,x^{2k-1}$ its Gram matrix $(\tau(x^{a+b}))$ vanishes for $a+b<2k-1$ and equals 1 for $a+b=2k-1$. Hence every $\mathbb{F}_2$-linear form on $R$ is $\tau(\varphi\cdot)$ for a unique $\varphi\in R$. Every linear form on $F\times F$ is $(z_1,z_2)\mapsto\operatorname{Tr}(Az_1+Bz_2)$; write $\tau(z)=\operatorname{Tr}(A_0z(\alpha)+B_0z(\alpha^{-1}))$. If $A_0=0$, then $\tau(zw)=0$ for $z=(1,0)$ and all $w$, contradicting nondegeneracy; so $A_0\ne0$, and likewise $B_0\ne0$. Put $\kappa=(A_0B_0)^{-1}$.

Let $\Lambda(z)=\operatorname{Tr}(Pz(\alpha)+Qz(\alpha^{-1}))$, so $s_i=\Lambda(x^i)$, and let $\varphi\in R$ with $\Lambda=\tau(\varphi\cdot)$. Comparing the two expressions of $\Lambda$ gives $P=A_0\varphi(\alpha)$ and $Q=B_0\varphi(\alpha^{-1})$, so $\varphi\in R^*$ and $\operatorname{Nm}(\varphi)=\kappa P Q$.

Now $s_{i+j}=\tau(x^i\varphi\cdot x^j)$. The annihilator $\mathcal{A}=\{w\in R:\tau(wx^j)=0,\ 0\le j<k\}$ of the $k$-dimensional space $P_k$ has dimension $k$, and it contains $P_k$, because for $\deg w<k$ and $j<k$ the product $wx^j$ has degree $\le2k-2$. Hence $\mathcal{A}=P_k$, and the window at $i$ is zero if and only if $h_i:=x^i\varphi\in P_k$.

Since $x$ has order $n$ in $R^*$ (its image is $(\alpha,\alpha^{-1})$), the elements $h_i$, $i\in\mathbb{Z}/n$, are distinct, and $\operatorname{Nm}(h_i)=\operatorname{Nm}(\varphi)$. Conversely, let $h\in P_k\setminus\{0\}$ with $\operatorname{Nm}(h)=\operatorname{Nm}(\varphi)$. Then $h(\alpha)/\varphi(\alpha)=\alpha^i$ for a unique $i\in\mathbb{Z}/n$, and $h(\alpha^{-1})=\operatorname{Nm}(\varphi)/h(\alpha)=\varphi(\alpha^{-1})\alpha^{-i}$, so $h=h_i$ in $R$. Thus $Z(P,Q)=\rho(\operatorname{Nm}\varphi)=\rho(\kappa P Q)$.

The norm form of $\mathbb{F}_2(x)/\mathbb{F}_2(s)$, $s=x+x^{-1}$

Let $A=\mathbb{F}_2[s]$ and $O=\mathbb{F}_2[x,x^{-1}]=A[x]$, where $x^2+sx+1=0$. The involution $x\mapsto x^{-1}$ fixes $s$, so for $h\in\mathbb{F}_2[x]$ there is a unique $N(h)\in A$ with $h(x)h(x^{-1})=N(h)(x+x^{-1})$. Put $\beta=\alpha+\alpha^{-1}$; then $\operatorname{Nm}(h)=N(h)(\beta)$.

References

The field $\mathbb{F}_2(\beta)$ is all of $F$: otherwise $k=2j$, $\beta\in\mathbb{F}_{2^j}$, and $\alpha,\alpha^{-1}$ are the two roots of $X^2+\beta X+1$ over $\mathbb{F}_{2^j}$, so $\alpha^{2^j}=\alpha^{-1}$ and $n\mid2^j+1$, which is impossible. Let $m_\beta\in A$ be the minimal polynomial of $\beta$ (irreducible, of degree $k$). Then $y\mapsto y(\beta)$ is a bijection from $P_k\subset A$ onto $F$, and from $P_\ell$ onto an $\mathbb{F}_2$-subspace $U_\ell$ of dimension $\ell$, for $\ell\le k$.

Define $\chi_0:A\to\{0,\pm1\}$ by $\chi_0(D)=0$ if $s\mid D$, and $\chi_0(D)=(-1)^{D_1}$ if $D=1+D_1s+\cdots$. It is completely multiplicative.

Proof. Write $h=x^ah_0$ with $h_0(0)=1$ and $e=\deg h_0$. Then $N(h)=N(h_0)$, and the Laurent polynomial $h_0(x)h_0(x^{-1})$ has extreme terms $x^{\pm e}$, so $N(h_0)$ has degree exactly $e\le\deg h<k$.

$O$ is a localisation of $\mathbb{F}_2[x]$, hence a principal ideal domain, integral over $A$; it is the integral closure of $A$ in $\mathbb{F}_2(x)$, and $N$ is the norm of the quadratic extension $\mathbb{F}_2(x)/\mathbb{F}_2(s)$. The units of $O$ are the monomials $x^j$, so each nonzero ideal of $O$ has a unique generator $h_0\in\mathbb{F}_2[x]$ with $h_0(0)=1$, and its norm is $N(h_0)A$. Hence $\#\{h_0:h_0(0)=1,\ N(h_0)=P\}$ is the number $a(P)$ of ideals of $O$ of norm $PA$. Since $O=A[x]$, the decomposition of a prime $Q$ of $A$ in $O$ follows that of $X^2+\overline{s}X+1$ over $A/Q$. For $Q=s$ this is $(X+1)^2$ (ramified). For $Q\ne s$ put $\theta=\overline{s}\ne0$; the polynomial is separable, and it has a root if and only if $Y^2+Y=\theta^{-2}$ does, i.e. iff $\operatorname{Tr}_{(A/Q)/\mathbb{F}_2}(\theta^{-1})=0$. This trace is the sum of the inverses of the roots of $Q=1+q_1s+\cdots$, namely $q_1$. Thus $Q$ splits iff $\chi_0(Q)=1$ and is inert iff $\chi_0(Q)=-1$, and the standard count gives $a=1*\chi_0$. Finally $h=x^ah_0$ with $\deg h<k$ allows $a\in\{0,\ldots,k-1-e\}$, which is $k-\deg P$ choices. □

Estimates in characteristic two

Proof. Let $f=\prod Q^{e_Q}$, $\deg f\le N$, and $L=\lceil(\log_2 N)/2\rceil\ge1$. There are at most $2^L\le2\sqrt{N}$ primes of degree $<L$, each contributing a factor $e_Q+1\le N+1$. Primes of degree $\ge L$ contribute

The next lemma is Bagshaw’s Lemma 5.3 [1], whose proof uses no hypothesis on $q$ and no exponential sums; we give it with explicit constants for $q=2$ and irreducible modulus.

Proof. Let $\widetilde a\in P_k$ with $\widetilde a(\beta)=a$, and $k_0=\lceil(k+\ell)/2\rceil-1\in[1,k-1]$. The linear map sending $u\in P_{k_0+1}$ to the coefficients of $s^{k-k_0},\ldots,s^{k-1}$ of $\widetilde au\bmod m_\beta$ goes from dimension $k_0+1$ to dimension $k_0$, so there is $u\ne0$, $\deg u\le k_0$, with $v:=\widetilde au\bmod m_\beta$ of degree $\le k-k_0-1$. Also $v\ne0$, as $m_\beta\nmid\widetilde a$ and $m_\beta\nmid u$. For a solution, $u(y_1+y_2)\equiv vy_1y_2\pmod{m_\beta}$, so $G:=u(y_1+y_2)+vy_1y_2=tm_\beta$ with $t\in A$, and $\deg G\le\max(k_0+\ell-1,k-k_0-1+2\ell-2)$. With

this gives $\deg t\le(3\ell-k-3)/2$, hence at most $1+2^{(3\ell-k)/2}$ possible $t$ (the term $1$ accounts for $t=0$). For fixed $t$,

and $N_t\ne0$, since otherwise $m_\beta\mid u$. The divisor $vy_1+u$ of $N_t$ determines $y_1$ and then $y_2$, and $\deg N_t\le3k$. So each $t$ accounts for at most $\tau_{3k}$ solutions. $\square$

Proof. $E(Y)\le E(P_\ell\setminus\{0\})=\sum_{a\in F}I(a)^2$ with $I(0)=2^\ell-1$ (in characteristic two $\overline{y}_1=\overline{y}_2$ iff $y_1=y_2$), and

Apply Lemma 10. $\square$

Proof. By Cauchy–Schwarz,

where $\nu(z)=\#\{(y_1,y_2)\in Y^2:\overline{y}_1+\overline{y}_2=z\}$. By Cauchy–Schwarz again and orthogonality,

$\square$

Proof of Theorem 1

By Corollary 6, $W(c)=\sum_{d+e\le k-1}(k-d-e)S_{d,e}$ with $S_{d,e}=\sum_{\deg D=d}\sum_{\deg E=e}\chi_0(D)\chi(\lambda\overline{D}\overline{E})$, $d,e\ge0$. There are at most $k(k+1)/2$ pairs and the weights are $\le k$, so $|W(c)|\le k^3\max_{d,e}|S_{d,e}|$. Each $S_{d,e}$ satisfies:

• (i) $|S_{d,e}|\le2^{d+e}$;

• (ii) $|S_{d,e}|\le2^d\cdot2^{k/2+3}$ and $|S_{d,e}|\le2^e\cdot2^{k/2+3}$ (fix one variable, Lemma 8);

• (iii) $|S_{d,e}|^4\le2^{3d+k}E(Y_e)\le12\tau_{3k}2^{3d+2e+k}\max\left(1,2^{(3e+3-k)/2}\right)$ (Lemmas 12 and 11, with $Y_e$ the polynomials of degree $e$, $Y_e\subseteq P_{e+1}$, and $1+\tau(1+z)\le3\tau\max(1,z)$).

Let $\eta=1/22$. If $\min(d,e)\le(1/2-\eta)k$, (ii) gives $|S_{d,e}|\le8\cdot2^{(1-\eta)k}$. If $d+e\le(1-\eta)k$, (i) gives $|S_{d,e}|\le2^{(1-\eta)k}$. Otherwise $\min(d,e)>(1/2-\eta)k$ and $d+e\le k-1$, so $\max(d,e)<(1/2+\eta)k$, and (iii) gives

because $k-d-2e<(-1/2+3\eta)k$ and $(k+3)/2-d-e/2<(-1/4+3\eta/2)k+3/2$. As $-\frac1{16}+\frac{3\eta}{8}=-\frac1{22}$ and $d+e<k$, we get $|S_{d,e}|\le(12\tau_{3k})^{1/4}2^{3/8}2^{21k/22}$. Hence $|W(c)|\le k^3C_k2^{21k/22}$ and Proposition 3 gives the theorem, with Lemma 9 for $\tau_{3k}$. $\square$

Fixed pattern, random codeword

For $w \in\mathbb{F}_2^k$ let $X_w$ be the random variable $c \mapsto N_w(S_c)$ on $\mathbb{F}^*$ with the uniform measure. It is conjectured in [5 §V-D] that $X_{w_k} \to\mathcal{P}(1)$ for almost every $(w_k) \in\prod_k \mathbb{F}_2^k$ (product of uniform measures); this fails for $w_k=0^k$.

Let $\psi:F\to F$ be the $\mathbb{F}_2$-linear bijection $g(\alpha)\mapsto g(\alpha^{-1})$ ($g\in P_k$), and for $\delta\in F$ put $\Phi_\delta(y)=y\psi(y)+\delta y$.

Proof. Keep the notation of the proof of Lemma 2, with $P=1$, $Q=c$. Let $A_w=\{z\in R:\tau(zx^j)=w_j,\ 0\leq j<k\}$. By nondegeneracy $A_w$ is a coset $z_w+P_k$ of the annihilator $P_k$, and $z_w$ may be chosen $\mathbb{F}_2$-linear in $w$. The window of $S_c$ at $i$ equals $w$ iff $x^i\varphi\in A_w$.

As in Lemma 2, the units $h\in A_w$ with $\operatorname{Nm}(h)=\operatorname{Nm}(\varphi)=\kappa c$ are exactly the elements $x^i\varphi\in A_w$, one for each such $i$. Write $(z_w(\alpha),z_w(\alpha^{-1}))=(p,q)$; for $g\in P_k$ with $g(\alpha)=y$,

with $y'=y+p$ and $\delta_w=\psi(p)+q$, which does not depend on the choice of $z_w$ in its coset. Every solution of $y'(\psi(y')+\delta_w)=\kappa c\ne0$ gives a unit. The map $w\mapsto\delta_w$ is linear, and $\delta_w=0$ iff $(p,q)$ lies in the image of $P_k$, i.e. iff $A_w=P_k$, i.e. iff $w=0$. Hence it is bijective. □

Thus the matrix $(N_w(S_c))_{w,c}$ is the matrix of fibre sizes $\#\Phi_\delta^{-1}(\lambda)$, $\delta\in F$, $\lambda\in F^*$: its rows ($c$ fixed) are the objects of Conjecture 35 of [5], its columns ($w$ fixed) those of [5 §V-D].

Proof. With $a=g(\alpha)$, $b=h(\alpha)$, $g,h\in P_k\setminus\{0\}$, the condition reads $B(g,h)(\beta)=0$ with $B(g,h)=N(g+h)+N(g)+N(h)\in A$ of degree $<k$; hence $B(g,h)=0$, i.e. $g(x)h(x^{-1})=h(x)g(x^{-1})$. Write $g=x^a d g_1$, $h=x^b d h_1$ with $d,g_1,h_1$ of constant term $1$ and $\gcd(g_1,h_1)=1$. Cancelling $d(x)d(x^{-1})$ and writing $f^*(x)=x^{\deg f}f(x^{-1})$, the condition becomes $x^{2(a-b)+\deg g_1-\deg h_1}g_1h_1^*=g_1^*h_1$; comparing constant terms, $2(a-b)=\deg h_1-\deg g_1$ and $g_1h_1^*=g_1^*h_1$, whence $g_1\mid g_1^*$, $g_1^*=g_1$ and $h_1^*=h_1$. There are at most $2^{e/2}$ palindromes of degree $e$ with constant term $1$, at most $2^\delta$ choices of $d$ of degree $\delta$, and at most $k$ choices of $(a,b)$ once the degrees are fixed. Hence

□

Remark 15. $\Sigma_0$ is the quantity computed exactly in [5 Lemma 7(1)]: $\Sigma_0=(3k-3)2^{k-2}+1$ for $k$ odd and $(3k-4)2^{k-2}+1$ for $k$ even. Lemma 14 is a self-contained weaker bound; with the exact value the constant $120k^3$ in Theorem 16(ii) becomes $8k^{3/2}$. The use of the spaces $E_\rho$ below parallels the proof of [5 Theorem 38].

Consequently, for almost every sequence $(w_k)\in\prod_k\mathbb{F}_2^k$, $\mathbb{E}[X_{w_k}]\to1$ and $\mathbb{E}[X_{w_k}(X_{w_k}-1)]\to1$.

Proof. Write $\delta=\delta_w$ and $\lambda=\kappa c$, which is uniform on $F^*$. (i) $\sum_{\lambda\ne0}\#\Phi_\delta^{-1}(\lambda)=2^k-\#\Phi_\delta^{-1}(0)$ and $\Phi_\delta^{-1}(0)=\{0,\psi^{-1}(\delta)\}$, of size $2$ for $\delta\ne0$.

(ii) Let $S(\delta)=\#\{(y,y'):y\ne y',\ \Phi_\delta(y)=\Phi_\delta(y')\}$; then $n\mathbb{E}[X_w(X_w-1)]=S(\delta)-2$ for $w\ne0$. For $a\ne0$, $\Phi_\delta(y+a)+\Phi_\delta(y)=\ell_a(y)+a\psi(a)+\delta a$ with $\ell_a(y)=y\psi(a)+a\psi(y)$, which is $\mathbb{F}_2$-linear in $y$. Let $d_a = \dim\ker\ell_a$ and $C_a = \{\delta: \delta a \in a\psi(a) + \operatorname{Im}\ell_a\}$, an affine subspace of codimension $d_a$ with direction $D_a = a^{-1}\operatorname{Im}\ell_a$. Then $S(\delta) = \sum_{a\ne0} 2^{d_a}1_{C_a}(\delta)$, whose mean over $\delta\in F$ is $m = \sum_{a\ne0}1 = n$.

Put $\rho(a) = \psi(a)/a$, $E_\rho= \{y : \psi(y) = \rho y\}$ and $E_\rho^* = \{\theta: \psi^*(\theta) = \rho\theta\}$, where $\psi^*$ is the adjoint of $\psi$ for $(u,v) \mapsto\operatorname{Tr}(uv)$. Then $\ker\ell_a = E_{\rho(a)}$. The adjoint of $\ell_a$ is $z \mapsto z\psi(a) + \psi^*(za)$, so $\theta\in D_a^\perp$ iff $\ell_a^*(\theta/a) = 0$ iff $\psi^*(\theta) = \rho(a)\theta$: $D_a^\perp= E_{\rho(a)}^*$. If $\rho(a) \ne\rho(b)$ then $D_a^\perp\cap D_b^\perp= 0$, so $D_a + D_b = F$ and $|C_a \cap C_b| = 2^{k-d_a-d_b}$. Therefore

where $v$ runs over the values of $\rho$ and $\{a:\rho(a)=v\}=E_v\setminus\{0\}$ has $2^{d_v}-1$ elements. Here $\sum_v(2^{d_v}-1)^2=\Sigma_0$ and $2^{d_v}\le2(2^{d_v}-1)\le2\Sigma_0^{1/2}$, so by Lemma 14 the sum is $\le2^{k+1}\Sigma_0^{3/2}\le30k^{3}25^{k/2}$. Since $|\mathbb{E}[X_w(X_w-1)]-1|\le|S(\delta_w)-m|/n+2/n$ for every $w$, $2/n\le2^{2-k}$ and $n^2\ge2^{2k-2}$, Chebyshev’s inequality gives (ii). The bound is summable in $k$, and so is $\Pr(w_k=0)=2^{-k}$; the last statement follows from the Borel–Cantelli lemma (applied with $\varepsilon=1/j$, $j=1,2,\ldots$) and (i). □

Numerical verification

The ancillary script VERIF_MELAS_M2.py (pure Python) checks:

• Proposition 3 against direct pattern counting, for every $c\in F^*$ and $4\le k\le10$ (a single constant $\kappa$ for all $c$);

• Proposition 5, for every $P$ with $\deg P<k$, $3\le k\le9$;

• the worst case $\max_c|M_2^{(k,c)}-1|$, for $k\le16$;

• Proposition 13 (equality of the multisets of columns $(N_w(S_c))_c$ and of fibre-size vectors of $\Phi_\delta$), for $k\le8$;

• Lemma 14, for $3\le k\le8$.

Corollary 6 was checked separately for $4\le k\le10$, on about fifty values of $c$ for each $k$. Observed values of $\max_c|M_2^{(k,c)}-1|$ (with the primitive polynomials listed in the script) are:

$k$	8	10	12	14	16	20
$\max_c|M_2-1|$	0.2969	0.2168	0.1245	0.0710	0.0439	0.0156

and $\max_c|W(c)|/2^{k/2}<k$ for $4\le k\le20$, consistent with square-root cancellation, which is far stronger than Theorem 1.

For the columns, the computed values of $\Sigma_0$ agree with [5 Lemma 7(1)], and the variance of $\mathbb{E}[X_w(X_w-1)]$ over $w\ne0$ is 0.158, 0.104, 0.063, 0.036 for $k=6,8,10,12$, while $\max_w\mathbb{E}[X_w(X_w-1)]\approx(k+1)/2$ in this range, so that the restriction to almost every $w$ in Theorem 16 cannot be dropped.

Status. Theorems 1 and 16: proved. Section 7: verified by computation. The full Conjecture 35 of [5] (all factorial moments, for every sequence $c_k$) remains open.

Acknowledgements. The conjectures, the correspondence between windows and polynomials [5 Theorems 12–13] and the count of [5 Lemma 7] are due to Sac Himelfarb and Schwartz. The energy bound follows Bogshav [1, 2] and Bourgain–Garaev [4]. Computations and drafting were assisted by Claude (Anthropic).

Meaux, France