Theorem A. After the conventions of § 3.0, read §§ 3.3 to 3.5 (Gauss sums of the weight form, their Poisson relation, and the odd characters), then § 3.10 (differences of the two halves of T T T ). The other lemmas are counts and congruences.
Self-duality. § 5 tests the criterion of [CKRS, Cor. 2.7] at every residue mod 8, with closed forms. The witnesses for the only if direction are z = 2 h ~ ′ z = 2\widetilde{h}^{\prime} z = 2 h ′ with h ′ ∈ R h^{\prime} \in R h ′ ∈ R of weight ≡ 2 ( m o d 4 ) \equiv2 \pmod{4} ≡ 2 ( mod 4 ) , and z = 1 z = 1 z = 1 (§ 5.4).
Why it matters. Formal duals of periodic non-lattice configurations were known for the family D n + ( α ) D_n^+(\alpha) D n + ( α ) , formally dual to D n + ( 1 / α ) D_n^+(1/\alpha) D n + ( 1/ α ) when n n n is odd or a multiple of four and not a lattice for odd n n n , and for P 6 P_6 P 6 [CKS]; for the TITO configuration, the family built from Gauss sums, and the configurations that [CKRS, Thm. 2.8] attaches to formally dual pairs in finite abelian groups, such as those of [LPS] and [KS]; and for Vardy’s 20-dimensional packing [CCV, § 5]. What this note adds is a closed formula for a formal dual of Γ ( C , C ⊥ ) \Gamma(C,C^\perp) Γ ( C , C ⊥ ) for every [ 2 k , k ] [2k,k] [ 2 k , k ] code C ≠ C ⊥ C \ne C^\perp C = C ⊥ , and the fact that this configuration is formally isodual.
Notation and definitions
Notation. n = 2 k n = 2k n = 2 k . For a binary word b b b , b ~ ∈ { 0 , 1 } n ⊂ Z n \tilde{b} \in\{0,1\}^{n} \subset\mathbb{Z}^{n} b ~ ∈ { 0 , 1 } n ⊂ Z n is its 0/1 lift; 1 1 1 is the all-ones vector; e 1 e_{1} e 1 the first unit vector; ζ = e 2 π i / 8 \zeta= e^{2\pi i/8} ζ = e 2 π i /8 ; for y ∈ Z n y \in\mathbb{Z}^{n} y ∈ Z n , χ y ( x ) = ζ ⟨ x , y ⟩ \chi_y(x) = \zeta^{\langle x,y\rangle} χ y ( x ) = ζ ⟨ x , y ⟩ . For a code C C C : R = C ∩ C ⊥ R = C \cap C^{\perp} R = C ∩ C ⊥ (hull), h = dim R h = \dim R h = dim R , r = k − h r = k-h r = k − h , and λ ( x ) = wt ( x ) / 2 m o d 2 \lambda(x) = \operatorname{wt}(x)/2 \bmod2 λ ( x ) = wt ( x ) /2 mod 2 for x ∈ R x \in R x ∈ R . For X X X in a finite abelian group, ν X ( g ) = # { ( a , b ) ∈ X 2 : a − b = g } \nu_X(g) = \#\{(a,b) \in X^2 : a-b = g\} ν X ( g ) = # {( a , b ) ∈ X 2 : a − b = g } . Following Bierbrauer–Edel [BE, p. 97] (two readings of [BE]; for 1 ∉ R 1 \notin R 1 ∈ / R the configuration (1) may differ from the packing of the p. 98 reading: §§ 10.1 and 10.3), for binary linear codes C 2 , C 2 ′ C_2,C'_2 C 2 , C 2 ′ of the same length,
Γ ( C 2 , C 2 ′ ) = Γ 8 + 8 Z n , Γ 8 = { − 2 b ~ + 4 c ~ : b ∈ 1 + C 2 , wt c even } ∪ { 1 − 2 b ~ + 4 c ~ : b ∈ C 2 ′ , wt c odd } ( m o d 8 ) (1) \Gamma(C_2,C'_2)=\Gamma_8+8\mathbb{Z}^n,
\qquad
\Gamma_8=\{ -2\widetilde{b}+4\widetilde{c}: b\in1+C_2,\ \operatorname{wt}c\ \text{even}\}
\cup\{1-2\widetilde{b}+4\widetilde{c}: b\in C'_2,\ \operatorname{wt}c\ \text{odd}\}\pmod{8} \tag*{(1)} Γ ( C 2 , C 2 ′ ) = Γ 8 + 8 Z n , Γ 8 = { − 2 b + 4 c : b ∈ 1 + C 2 , wt c even } ∪ { 1 − 2 b + 4 c : b ∈ C 2 ′ , wt c odd } ( mod 8 ) (1)
Formal duality: [CKRS, Def. 2.1] for periodic configurations in R n \mathbb{R}^n R n ; [CKRS, Def. 2.9 and Thm. 2.8] for subsets S ⊂ H S\subset H S ⊂ H , T ⊂ H ^ T\subset\widehat{H} T ⊂ H of a finite abelian group: ∣ T ∣ ∣ S ^ ( χ ) ∣ 2 = ∣ S ∣ 2 ν T ( χ ) |T||\widehat{S}(\chi)|^2=|S|^2\nu_T(\chi) ∣ T ∣∣ S ( χ ) ∣ 2 = ∣ S ∣ 2 ν T ( χ ) for every χ \chi χ , and the symmetric identity.
Statements
Theorem A. Let C ⊂ F 2 n C\subset\mathbb{F}_2^n C ⊂ F 2 n be a binary linear [ n , k ] [n,k] [ n , k ] code, n = 2 k n=2k n = 2 k , with C ≠ C ⊥ C\ne C^\perp C = C ⊥ , and Γ = Γ ( C , C ⊥ ) \Gamma=\Gamma(C,C^\perp) Γ = Γ ( C , C ⊥ ) . Choose
u ∈ F 2 n u\in\mathbb{F}_2^n u ∈ F 2 n with u ⋅ x = λ ( x ) u\cdot x=\lambda(x) u ⋅ x = λ ( x ) for every x ∈ R x\in R x ∈ R ;
w ∈ C w\in C w ∈ C with w ⋅ c ≡ wt ( c ) ( m o d 2 ) w\cdot c\equiv\operatorname{wt}(c)\pmod{2} w ⋅ c ≡ wt ( c ) ( mod 2 ) for every c ∈ C c\in C c ∈ C (w = 0 w=0 w = 0 if C C C is even);
ε ≡ n / 2 + 1 ( m o d 2 ) \varepsilon\equiv n/2+1\pmod{2} ε ≡ n /2 + 1 ( mod 2 ) .
Let L ′ = 8 Z n + ∑ j Z 4 ( e 1 + e j ) + ∑ x ∈ R Z 2 x ~ L'=8\mathbb{Z}^n+\sum_j\mathbb{Z}\,4(e_1+e_j)+\sum_{x\in R}\mathbb{Z}\,2\widetilde{x} L ′ = 8 Z n + ∑ j Z 4 ( e 1 + e j ) + ∑ x ∈ R Z 2 x , A = ⟨ Γ − Γ ⟩ A=\langle\Gamma-\Gamma\rangle A = ⟨ Γ − Γ ⟩ , H ′ = A / L ′ H'=A/L' H ′ = A / L ′ , x 0 ∈ Γ x_0\in\Gamma x 0 ∈ Γ , S = ( Γ − x 0 ) / L ′ ⊂ H ′ S=(\Gamma-x_0)/L'\subset H' S = ( Γ − x 0 ) / L ′ ⊂ H ′ , and
T = { 2 c ~ + 4 ( u ⋅ c ) e 1 : c ∈ C } ∪ { 1 + 2 ( u ~ + w ~ ) + 2 d ~ + 4 ( ε + u ⋅ d ) e 1 : d ∈ C ⊥ } , (2) T=\{2\widetilde{c}+4(u\cdot c)e_1:c\in C\}\cup\{1+2(\widetilde{u}+\widetilde{w})+2\widetilde{d}+4(\varepsilon+u\cdot d)e_1:d\in C^\perp\}, \tag*{(2)} T = { 2 c + 4 ( u ⋅ c ) e 1 : c ∈ C } ∪ { 1 + 2 ( u + w ) + 2 d + 4 ( ε + u ⋅ d ) e 1 : d ∈ C ⊥ } , (2) each vector y y y being read as the character χ y \chi_y χ y of H ′ H' H ′ . Then:
L ′ L' L ′ is a lattice of periods of Γ \Gamma Γ ; ∣ S ∣ = 2 r + 1 |S|=2^{r+1} ∣ S ∣ = 2 r + 1 , ∣ H ′ ∣ = 2 2 r + 2 |H'|=2^{2r+2} ∣ H ′ ∣ = 2 2 r + 2 , and T T T is a set of 2 r + 1 2^{r+1} 2 r + 1 distinct characters of H ′ H' H ′ (the two halves of (2) have disjoint images, and within each half every class of its image has exactly 2 h 2^h 2 h preimages).
S ⊂ H ′ S\subset H' S ⊂ H ′ and T ⊂ H ′ ^ T\subset\widehat{H'} T ⊂ H ′ are formally dual (both identities, for every character and every group element).
Hence Γ \Gamma Γ and Q = A ∗ + T / 8 Q=A^*+T/8 Q = A ∗ + T /8 are formally dual in R n \mathbb{R}^n R n [CKRS, Thm. 2.8] with Λ = L ′ \Lambda=L' Λ = L ′ , equivalently [Cor. 2.7]; the lattice of Q Q Q is A ∗ A^* A ∗ , and y ∈ Z n y\in\mathbb{Z}^n y ∈ Z n stands for the character y / 8 + A ∗ y/8+A^* y /8 + A ∗ of L ′ ∗ / A ∗ L'{}^*/A^* L ′ ∗ / A ∗ , where
A ∗ = 1 4 { z ∈ Z n : z m o d 2 ∈ R , ∑ i z i ≡ 0 ( m o d 4 ) } . (3) A^*=\frac{1}{4}\{z\in\mathbb{Z}^n:z\bmod2\in R,\ \sum_i z_i\equiv0\pmod{4}\}. \tag*{(3)} A ∗ = 4 1 { z ∈ Z n : z mod 2 ∈ R , i ∑ z i ≡ 0 ( mod 4 )} . (3) ν T \nu_T ν T takes the value 2 r + 1 2^{r+1} 2 r + 1 once (at 0 0 0 ), 2 r − 1 2^{r-1} 2 r − 1 on a family of 4 ( 2 r − 1 ) 4(2^r-1) 4 ( 2 r − 1 ) characters, 2 2 2 on a disjoint family of 2 2 r 2^{2r} 2 2 r characters, and 0 0 0 elsewhere; for r = 2 r=2 r = 2 the two values coincide, so ν T = 2 \nu_T=2 ν T = 2 on 28 characters. H ′ ^ \widehat{H'} H ′ is elementary abelian if and only if 1 ∈ R 1\in R 1 ∈ R .
The pair ( S , T ) (S,T) ( S , T ) is primitive in the sense of Kölsch–Schüler [KS]: neither set lies in a coset of a proper subgroup, and neither is a union of cosets of a non-trivial subgroup.
If 1 ∈ R 1\in R 1 ∈ R , the dot product is alternating on C / R C/R C / R , so r r r is even.
Proposition I: (C,C) is formally isodual
Proposition I. Keep the hypotheses and notation of Theorem A, with ( u , w ) (u,w) ( u , w ) admissible (chosen as in Theorem A). Let f ∈ R ⊥ = C + C ⊥ f \in R^\perp= C + C^\perp f ∈ R ⊥ = C + C ⊥ with wt ( u + f ) ≡ n / 2 ( m o d 2 ) \operatorname{wt}(u+f) \equiv n/2 \pmod{2} wt ( u + f ) ≡ n /2 ( mod 2 ) ; write f = c 0 + e f=c_0+e f = c 0 + e with c 0 ∈ C c_0 \in C c 0 ∈ C , e ∈ C ⊥ e \in C^\perp e ∈ C ⊥ (any decomposition); put D = u + f D=u+f D = u + f , choose v ∈ F 2 n v \in\mathbb{F}_2^n v ∈ F 2 n with wt v ≡ wt c 0 ( m o d 2 ) \operatorname{wt} v \equiv\operatorname{wt} c_0 \pmod{2} wt v ≡ wt c 0 ( mod 2 ) , and set
τ = 2 ( 1 ~ − c 0 ~ ) + 4 v ~ , g ( x ) = σ D x + τ , (4) \tau= 2(\widetilde{1}-\widetilde{c_0})+4\widetilde{v}, \qquad g(x)=\sigma_D x+\tau, \tag*{(4)} τ = 2 ( 1 − c 0 ) + 4 v , g ( x ) = σ D x + τ , (4) where σ D \sigma_D σ D changes the sign of the coordinates in supp D \operatorname{supp} D supp D .
g ( 8 Q ) = Γ g(8Q)=\Gamma g ( 8 Q ) = Γ , as subsets of R n \mathbb{R}^n R n .
Such an f f f exists for every admissible ( C , u , w ) (C,u,w) ( C , u , w ) : if 1 ∈ R 1 \in R 1 ∈ R every f f f works (for instance f = 0 f=0 f = 0 with c 0 = v = 0 c_0=v=0 c 0 = v = 0 , which gives g ( x ) = σ u x + 2 ⋅ 1 g(x)=\sigma_u x+2\cdot1 g ( x ) = σ u x + 2 ⋅ 1 ); if 1 ∉ R 1 \notin R 1 ∈ / R , R ⊥ R^\perp R ⊥ contains odd-weight words.
Hence Q = σ D ( Γ − τ ) / 8 Q=\sigma_D(\Gamma-\tau)/8 Q = σ D ( Γ − τ ) /8 is isometric to Γ / 8 \Gamma/8 Γ/8 , and P = Γ / ( 2 2 ) P=\Gamma/(2\sqrt{2}) P = Γ/ ( 2 2 ) , which has density 1, is formally dual to the isometric copy σ D ( P − τ ) / ( 2 2 ) \sigma_D(P-\tau)/(2\sqrt{2}) σ D ( P − τ ) / ( 2 2 ) of itself: P P P is formally isodual in the sense of Cohn–Kumar–Schürmann [CKS].
Items 1 and 2 use no external result; item 3 rests on Theorem A, item 3, and on [CKRS, Lemma 2.4] with φ = I / ( 2 2 ) \varphi=I/(2\sqrt{2}) φ = I / ( 2 2 ) .
Stealth radius
By [CCV, § 5.1], when two configurations of density 1 are formally dual, the stealth radius of one (in the sense of [CCV, § 2], for the stationary process obtained by a random translation, no factor 2 π 2\pi 2 π ) equals the minimal distance of the other. With Proposition I, the stealth radius at unit density of the dual is the minimal distance of the packing at unit density:
stealth ( Q unit density ) = d min ( P ) = d min ( Γ ) 2 2 . (5) \operatorname{stealth}(Q_{\text{unit density}})=d_{\min}(P)=\frac{d_{\min}(\Gamma)}{2\sqrt{2}}. \tag*{(5)} stealth ( Q unit density ) = d m i n ( P ) = 2 2 d m i n ( Γ ) . (5)
Remark on formal self-duality
Remark (formal self-duality). Status: proved on paper; both directions passed three hostile reviews. Call R R R doubly even if every word of R R R has weight divisible by 4. With P = Γ / ( 2 2 ) P=\Gamma/(2\sqrt{2}) P = Γ/ ( 2 2 ) as in Proposition I, P P P is formally self-dual in the sense of [CKS] (formally dual to itself, equivalently to a translate of P P P or of − P -P − P ) if and only if 4 ∣ n 4 \mid n 4 ∣ n and R R R is doubly even. The only if direction does not use Theorem A. The if direction is the case D = 0 D=0 D = 0 of Proposition I; it was reviewed in that form, which uses Theorem A, item 3, by all three reviews (conditionally on Theorem A, item 3, and Proposition I, item 1), and in a direct proof that does not use Theorem A by the second and third; the third review redid both directions without Theorem A, and its argument does not use C ≠ C ⊥ C \ne C^\perp C = C ⊥ . A related pattern in n n n mod 4 appears in Cohn, Kumar and Schürmann’s result for the two-coset structure D n + D_n^+ D n + , which is formally self-dual when n n n is odd or a multiple of four and formally isodual when n ≡ 2 ( m o d 4 ) n \equiv2 \pmod{4} n ≡ 2 ( mod 4 ) [CKS, § 6, Proposition 1; lines 621–623 of the source of arXiv:0911.2169v2]. For the codes of 18.1, 28.1 and 30.1 the hulls have weight sets { 0 , 18 } \{0,18\} { 0 , 18 } , { 0 , 14 , 28 } \{0,14,28\} { 0 , 14 , 28 } and { 0 , 10 , 20 , 30 } \{0,10,20,30\} { 0 , 10 , 20 , 30 } , none doubly even, and n / 2 n/2 n /2 is odd for n = 18 , 30 n=18,30 n = 18 , 30 . These three packings are therefore formally isodual and not formally self-dual. This last step uses the codes extracted from the coordinates of the packings of recordpackings.toml [RP] by two independent programs (§ 8.3), which give the same hull weights.
A worked example: n = 2 n=2 n = 2
Take k = 1 k=1 k = 1 and C = { 00 , 10 } C=\{00,10\} C = { 00 , 10 } , so C ⊥ = { 00 , 01 } C^\perp=\{00,01\} C ⊥ = { 00 , 01 } , R = { 00 } R=\{00\} R = { 00 } , h = 0 h=0 h = 0 , r = 1 r=1 r = 1 , and 1 ∉ R 1\notin R 1 ∈ / R . Every u ∈ F 2 2 u\in\mathbb{F}_2^2 u ∈ F 2 2 is admissible because R = 0 R=0 R = 0 ; we take u = 11 u=11 u = 11 , so that no term of (2) vanishes. The only w ∈ C w\in C w ∈ C with w ⋅ c ≡ wt ( c ) w\cdot c\equiv\operatorname{wt}(c) w ⋅ c ≡ wt ( c ) is w = 10 w=10 w = 10 . Here ε ≡ n / 2 + 1 ≡ 0 \varepsilon\equiv n/2+1\equiv0 ε ≡ n /2 + 1 ≡ 0 . Everything below was computed by an exact script (integers and Z [ ζ 8 ] \mathbb{Z}[\zeta_8] Z [ ζ 8 ] ) that applies (1) to (5) as written, and every identity was also run for the four values of u u u .
The configuration. By (1), with 0/1 lifts, Γ 8 \Gamma_8 Γ 8 has 8 = 2 n + k 8=2^{n+k} 8 = 2 n + k points mod 8. The even half (b ∈ { 11 , 01 } b\in\{11,01\} b ∈ { 11 , 01 } , wt c \operatorname{wt}c wt c even) is ( 0 , 6 ) , ( 2 , 2 ) , ( 4 , 2 ) , ( 6 , 6 ) (0,6),(2,2),(4,2),(6,6) ( 0 , 6 ) , ( 2 , 2 ) , ( 4 , 2 ) , ( 6 , 6 ) . The odd half (b ∈ C ⊥ b\in C^\perp b ∈ C ⊥ , wt c \operatorname{wt}c wt c odd) is ( 1 , 3 ) , ( 1 , 5 ) , ( 5 , 1 ) , ( 5 , 7 ) (1,3),(1,5),(5,1),(5,7) ( 1 , 3 ) , ( 1 , 5 ) , ( 5 , 1 ) , ( 5 , 7 ) .
The finite group. L ′ L' L ′ is generated by ( 8 , 0 ) (8,0) ( 8 , 0 ) and ( 4 , 4 ) (4,4) ( 4 , 4 ) , and A = ⟨ Γ − Γ ⟩ = { x ∈ Z 2 : x 1 ≡ x 2 ( m o d 2 ) } A=\langle\Gamma-\Gamma\rangle=\{x\in\mathbb{Z}^2:x_1\equiv x_2\pmod2\} A = ⟨ Γ − Γ ⟩ = { x ∈ Z 2 : x 1 ≡ x 2 ( mod 2 )} has basis a 1 = ( 2 , 0 ) a_1=(2,0) a 1 = ( 2 , 0 ) , a 2 = ( 1 , 1 ) a_2=(1,1) a 2 = ( 1 , 1 ) . The coordinates ( c 1 , c 2 ) = ( ( x 1 − x 2 ) / 2 , x 2 ) (c_1,c_2)=((x_1-x_2)/2,x_2) ( c 1 , c 2 ) = (( x 1 − x 2 ) /2 , x 2 ) identify H ′ = A / L ′ H'=A/L' H ′ = A / L ′ with Z 4 2 \mathbb{Z}_4^2 Z 4 2 , of order 16 = 2 2 r + 2 16=2^{2r+2} 16 = 2 2 r + 2 (not elementary abelian, as 1 ∉ R 1\notin R 1 ∈ / R ). With x 0 = ( 0 , 6 ) x_0=(0,6) x 0 = ( 0 , 6 ) we get S = { ( 0 , 0 ) , ( 1 , 3 ) , ( 2 , 1 ) , ( 3 , 0 ) } S=\{(0,0),(1,3),(2,1),(3,0)\} S = {( 0 , 0 ) , ( 1 , 3 ) , ( 2 , 1 ) , ( 3 , 0 )} , so ∣ S ∣ = 4 = 2 r + 1 |S|=4=2^{r+1} ∣ S ∣ = 4 = 2 r + 1 .
The set T T T . A vector y y y with y 1 + y 2 y_1+y_2 y 1 + y 2 even is the character χ ( c 1 , c 2 ) = i a c 1 + b c 2 \chi(c_1,c_2)=i^{ac_1+bc_2} χ ( c 1 , c 2 ) = i a c 1 + b c 2 with a ≡ y 1 a\equiv y_1 a ≡ y 1 , b ≡ ( y 1 + y 2 ) / 2 ( m o d 4 ) b\equiv(y_1+y_2)/2\pmod4 b ≡ ( y 1 + y 2 ) /2 ( mod 4 ) (our labelling). In (2), 2 ( u + w ~ ) 2(\widetilde{u+w}) 2 ( u + w ) lifts the sum u + w = 01 u+w=01 u + w = 01 , so it equals ( 0 , 2 ) (0,2) ( 0 , 2 ) , not 2 u ~ + 2 w ~ = ( 4 , 2 ) 2\widetilde{u}+2\widetilde{w}=(4,2) 2 u + 2 w = ( 4 , 2 ) . The other reading breaks both identities (checked); here it gives the same set T T T as flipping ε \varepsilon ε . We get
T = { ( 0 , 0 ) , ( 6 , 0 ) } ∪ { ( 1 , 3 ) , ( 5 , 5 ) } , T=\{(0,0),(6,0)\}\cup\{(1,3),(5,5)\}, T = {( 0 , 0 ) , ( 6 , 0 )} ∪ {( 1 , 3 ) , ( 5 , 5 )} ,
that is the characters ( a , b ) = ( 0 , 0 ) , ( 2 , 3 ) , ( 1 , 2 ) , ( 1 , 1 ) (a,b)=(0,0),(2,3),(1,2),(1,1) ( a , b ) = ( 0 , 0 ) , ( 2 , 3 ) , ( 1 , 2 ) , ( 1 , 1 ) , which are distinct.
Both identities. Here ∣ T ∣ ∣ S ^ ( χ ) ∣ 2 = 4 ∣ S ^ ( χ ) ∣ 2 |T||\widehat{S}(\chi)|^2=4|\widehat{S}(\chi)|^2 ∣ T ∣∣ S ( χ ) ∣ 2 = 4∣ S ( χ ) ∣ 2 and ∣ S ∣ 2 ν T ( χ ) = 16 ν T ( χ ) |S|^2\nu_T(\chi)=16\nu_T(\chi) ∣ S ∣ 2 ν T ( χ ) = 16 ν T ( χ ) . The 16 characters fall into four classes.
Table 1.
So 4 ∣ S ^ ∣ 2 = 16 ν T 4|\widehat{S}|^2=16\nu_T 4∣ S ∣ 2 = 16 ν T in every class. For r = 1 r=1 r = 1 item 4 predicts 2 r + 1 = 4 2^{r+1}=4 2 r + 1 = 4 once, 2 r − 1 = 1 2^{r-1}=1 2 r − 1 = 1 on 4 ( 2 r − 1 ) = 4 4(2^r-1)=4 4 ( 2 r − 1 ) = 4 characters and 2 on 2 2 r = 4 2^{2r}=4 2 2 r = 4 characters: this is what we see, and the values 1 and 2 do not coincide here. The symmetric identity ∣ S ∣ ∣ T ^ ( x ) ∣ 2 = ∣ T ∣ 2 ν S ( x ) |S||\widehat{T}(x)|^2=|T|^2\nu_S(x) ∣ S ∣∣ T ( x ) ∣ 2 = ∣ T ∣ 2 ν S ( x ) holds on all 16 elements: ∣ T ^ ( x ) ∣ 2 = 16 , 8 , 4 , 0 |\widehat{T}(x)|^2=16,8,4,0 ∣ T ( x ) ∣ 2 = 16 , 8 , 4 , 0 on 1, 4, 4, 7 elements, and ν S = 4 , 2 , 1 , 0 \nu_S=4,2,1,0 ν S = 4 , 2 , 1 , 0 on the same elements. With ε = 1 \varepsilon=1 ε = 1 instead, the first identity fails on 8 of the 16 characters.
The dual configuration. By (3), A ∗ = 1 4 { z : z even , z 1 + z 2 ≡ 0 ( m o d 4 ) } = 1 2 D 2 A^*=\frac{1}{4}\{z:z\text{ even},\ z_1+z_2\equiv0\pmod4\}=\frac{1}{2}D_2 A ∗ = 4 1 { z : z even , z 1 + z 2 ≡ 0 ( mod 4 )} = 2 1 D 2 , which contains Z 2 \mathbb{Z}^2 Z 2 . Hence 8 Q = 8 A ∗ + T 8Q=8A^*+T 8 Q = 8 A ∗ + T is 8 Z 2 8\mathbb{Z}^2 8 Z 2 -periodic, with residues mod 8
( 0 , 0 ) , ( 6 , 0 ) , ( 1 , 3 ) , ( 5 , 5 ) , ( 4 , 4 ) , ( 2 , 4 ) , ( 5 , 7 ) , ( 1 , 1 ) . (0,0),(6,0),(1,3),(5,5),(4,4),(2,4),(5,7),(1,1). ( 0 , 0 ) , ( 6 , 0 ) , ( 1 , 3 ) , ( 5 , 5 ) , ( 4 , 4 ) , ( 2 , 4 ) , ( 5 , 7 ) , ( 1 , 1 ) .
Proposition I. Take f = 10 = c 0 + e f=10=c_0+e f = 10 = c 0 + e with c 0 = 10 c_0=10 c 0 = 10 , e = 00 e=00 e = 00 , so D = u + f = 01 D=u+f=01 D = u + f = 01 has weight 1 ≡ n / 2 1\equiv n/2 1 ≡ n /2 . Take v = 10 v=10 v = 10 . Then τ = 2 ( 1 ~ − c 0 ~ ) + 4 v ~ = ( 0 , 2 ) + ( 4 , 0 ) = ( 4 , 2 ) \tau=2(\widetilde{1}-\widetilde{c_0})+4\widetilde{v}=(0,2)+(4,0)=(4,2) τ = 2 ( 1 − c 0 ) + 4 v = ( 0 , 2 ) + ( 4 , 0 ) = ( 4 , 2 ) and g ( x 1 , x 2 ) = ( x 1 + 4 , 2 − x 2 ) g(x_1,x_2)=(x_1+4,2-x_2) g ( x 1 , x 2 ) = ( x 1 + 4 , 2 − x 2 ) . The eight residues above go to
( 4 , 2 ) , ( 2 , 2 ) , ( 5 , 7 ) , ( 1 , 5 ) , ( 0 , 6 ) , ( 6 , 6 ) , ( 1 , 3 ) , ( 5 , 1 ) , (4,2),(2,2),(5,7),(1,5),(0,6),(6,6),(1,3),(5,1), ( 4 , 2 ) , ( 2 , 2 ) , ( 5 , 7 ) , ( 1 , 5 ) , ( 0 , 6 ) , ( 6 , 6 ) , ( 1 , 3 ) , ( 5 , 1 ) ,
which is exactly Γ 8 \Gamma_8 Γ 8 . Since $8Q$ is 8 Z 2 8\mathbb{Z}^2 8 Z 2 -periodic, g ( 8 Q ) = Γ g(8Q)=\Gamma g ( 8 Q ) = Γ as subsets of R 2 \mathbb{R}^2 R 2 . Also Γ \Gamma Γ has density 8 / 8 2 = 1 / 8 8/8^2=1/8 8/ 8 2 = 1/8 , and ( 2 2 ) 2 = 8 (2\sqrt{2})^2=8 ( 2 2 ) 2 = 8 , so P = Γ / ( 2 2 ) P=\Gamma/(2\sqrt{2}) P = Γ/ ( 2 2 ) has density 1. The minimal squared distance of $\Gamma is 2 (for instance (0, 6) and (1, 5)), so by (5) the stealth radius at unit density is 2 / 8 = 1 / 2 \sqrt{2/8}=1/2 2/8 = 1/2 . As 4 ∤ n 4 \nmid n 4 ∤ n , the remark of § 2.4 says that P P P is formally isodual and not formally self-dual.
What it shows. The finite pair of Theorem A and the map g g g of Proposition I can be checked by hand in dimension 2, including the readings of the lifts. For r = 1 r=1 r = 1 the finite pair is equivalent to a product of two TITO pairs, see § 8.2 and Row 5 of § 7 , so this example illustrates the formulas and is not a new object.
Proof of Theorem A
The hypotheses used are n = 2 k n=2k n = 2 k , C ′ = C ⊥ C^{\prime}=C^{\perp} C ′ = C ⊥ and h < k h<k h < k (that is, C ≠ C ⊥ C\ne C^{\perp} C = C ⊥ ); nothing else. The proof computes the Fourier transform of Γ \Gamma Γ (§ 3.2 to § 3.6 ), identifies the dual group (§ 3.7 ), and compares the result with the pair counts of T T T (§ 3.8 to § 3.12 ). Items 3, 4 and 5 follow in § 3.13 to § 3.15 . The heart of the proof is § 3.6 (odd characters) and § 3.10 (the differences between the two halves of T T T ).
Conventions and elementary facts
For a statement P P P , [ P ] [P] [ P ] is 1 if P P P holds and 0 otherwise. L ′ ∗ L^{\prime*} L ′ ∗ and A ∗ A^* A ∗ denote dual lattices. The function λ ( x ) = wt ( x ) / 2 m o d 2 \lambda(x)=\operatorname{wt}(x)/2 \bmod2 λ ( x ) = wt ( x ) /2 mod 2 is defined on any word of even weight. Binary words are read in F 2 n \mathbb{F}_2^n F 2 n , and in sums and weights also through their 0/1 lift. For y ∈ Z n y\in\mathbb{Z}^n y ∈ Z n write y ˉ = y m o d 2 ∈ F 2 n \bar{y}=y\bmod2\in\mathbb{F}_2^n y ˉ = y mod 2 ∈ F 2 n and Σ y = ∑ i y i \Sigma y=\sum_i y_i Σ y = ∑ i y i . For z ∈ ( Z / 4 ) n z\in(\mathbb{Z}/4)^n z ∈ ( Z /4 ) n write z = z ˉ + 2 z 1 z=\bar{z}+2z_1 z = z ˉ + 2 z 1 digitwise, with z 1 ∈ F 2 n z_1\in\mathbb{F}_2^n z 1 ∈ F 2 n ; then Σ z ≡ wt z ˉ + 2 wt z 1 ( m o d 4 ) \Sigma z\equiv\operatorname{wt}\bar{z}+2\operatorname{wt}z_1\pmod4 Σ z ≡ wt z ˉ + 2 wt z 1 ( mod 4 ) . We write Γ 8 \Gamma_8 Γ 8 for the set of residues of Γ \Gamma Γ mod 8, E E E for its even half and O O O for its odd half, so Γ 8 = E ∪ O \Gamma_8=E\cup O Γ 8 = E ∪ O with
E = { − 2 b ~ + 4 c ~ : b ∈ 1 + C , wt c even } , O = { 1 − 2 a ~ + 4 c ~ : a ∈ C ⊥ , wt c odd } . E=\{-2\tilde{b}+4\tilde{c}: b\in1+C,\ \operatorname{wt}c\text{ even}\},\qquad O=\{1-2\tilde{a}+4\tilde{c}: a\in C^{\perp},\ \operatorname{wt}c\text{ odd}\}. E = { − 2 b ~ + 4 c ~ : b ∈ 1 + C , wt c even } , O = { 1 − 2 a ~ + 4 c ~ : a ∈ C ⊥ , wt c odd } .
The characters of ( Z / 8 ) n (\mathbb{Z}/8)^n ( Z /8 ) n are the χ y \chi_y χ y , y ∈ ( Z / 8 ) n y\in(\mathbb{Z}/8)^n y ∈ ( Z /8 ) n , and S ^ 8 ( y ) = ∑ x ∈ Γ 8 χ y ( x ) \widehat{S}_8(y)=\sum_{x\in\Gamma_8}\chi_y(x) S 8 ( y ) = ∑ x ∈ Γ 8 χ y ( x ) .
(F1) For binary words a , b a,b a , b : wt ( a + b ) = wt a + wt b − 2 ∣ a ∩ b ∣ \operatorname{wt}(a+b)=\operatorname{wt}a+\operatorname{wt}b-2|a\cap b| wt ( a + b ) = wt a + wt b − 2∣ a ∩ b ∣ , hence wt ( a + b ) ≡ wt a + wt b + 2 a ⋅ b ( m o d 4 ) \operatorname{wt}(a+b)\equiv\operatorname{wt}a+\operatorname{wt}b+2\,a\cdot b\pmod4 wt ( a + b ) ≡ wt a + wt b + 2 a ⋅ b ( mod 4 ) . For several words, apply this repeatedly.
(F2) The hull R = C ∩ C ⊥ R=C\cap C^{\perp} R = C ∩ C ⊥ is self-orthogonal, so its words are even (x ⋅ x ≡ wt x x\cdot x\equiv\operatorname{wt}x x ⋅ x ≡ wt x ). By (F1), wt ( x + x ′ ) ≡ wt x + wt x ′ ( m o d 4 ) \operatorname{wt}(x+x')\equiv\operatorname{wt}x+\operatorname{wt}x'\pmod4 wt ( x + x ′ ) ≡ wt x + wt x ′ ( mod 4 ) for x , x ′ ∈ R x,x'\in R x , x ′ ∈ R , so λ \lambda λ is linear on R R R , and wt x ≡ 2 λ ( x ) ( m o d 4 ) \operatorname{wt}x\equiv2\lambda(x)\pmod4 wt x ≡ 2 λ ( x ) ( mod 4 ) for x ∈ R x\in R x ∈ R . Also R ⊥ = C + C ⊥ R^{\perp}=C+C^{\perp} R ⊥ = C + C ⊥ and 1 ∈ R ⊥ 1\in R^{\perp} 1 ∈ R ⊥ .
(F3) The words u u u and w w w of Theorem A exist. A linear form on R R R is x ↦ u ⋅ x x\mapsto u\cdot x x ↦ u ⋅ x for some u u u , which gives u u u . For w w w : write 1 = w + w ′ 1=w+w' 1 = w + w ′ with w ∈ C w\in C w ∈ C , w ′ ∈ C ⊥ w'\in C^{\perp} w ′ ∈ C ⊥ ; for c ∈ C c\in C c ∈ C , w ⋅ c = 1 ⋅ c = wt c ( m o d 2 ) w\cdot c=1\cdot c=\operatorname{wt}c\pmod2 w ⋅ c = 1 ⋅ c = wt c ( mod 2 ) . The admissible w w w form a coset of R R R . If C C C is even they are exactly the elements of R R R , since w ⋅ c = 0 w\cdot c=0 w ⋅ c = 0 on C C C means w ∈ C ⊥ w\in C^{\perp} w ∈ C ⊥ . Two consequences used below: 1 + w ∈ C ⊥ 1+w\in C^{\perp} 1 + w ∈ C ⊥ , and w ⋅ x = 0 w\cdot x=0 w ⋅ x = 0 for x ∈ R x\in R x ∈ R .
(F4) The maps ( b , c ) ↦ − 2 b ~ + 4 c ~ (b,c)\mapsto-2\tilde{b}+4\tilde{c} ( b , c ) ↦ − 2 b ~ + 4 c ~ and ( a , c ) ↦ 1 − 2 a ~ + 4 c ~ (a,c)\mapsto1-2\tilde{a}+4\tilde{c} ( a , c ) ↦ 1 − 2 a ~ + 4 c ~ are injective mod 8 (the four values of ( b i , c i ) (b_i,c_i) ( b i , c i ) give four distinct residues mod 8, and likewise for ( a i , c i ) (a_i,c_i) ( a i , c i ) ), and E , O E,O E , O are disjoint (parity of the coordinates). So ∣ E ∣ = ∣ O ∣ = 2 2 k − 1 |E|=|O|=2^{2k-1} ∣ E ∣ = ∣ O ∣ = 2 2 k − 1 and ∣ Γ 8 ∣ = 2 n + k = 2 3 k |\Gamma_8|=2^{n+k}=2^{3k} ∣ Γ 8 ∣ = 2 n + k = 2 3 k . Equivalently, writing a point as 2 y 2y 2 y or 1 + 2 y 1+2y 1 + 2 y with y ∈ ( Z / 4 ) n y\in(\mathbb{Z}/4)^n y ∈ ( Z /4 ) n ,
E = { 2 y : y ˉ ∈ 1 + C , Σ y ≡ − wt y ˉ } , O = { 1 + 2 y : y ˉ ∈ C ⊥ , Σ y ≡ 2 − wt y ˉ } ( m o d 4 ) E=\{2y:\ \bar{y}\in1+C,\ \Sigma y\equiv-\operatorname{wt}\bar{y}\},\qquad O=\{1+2y:\ \bar{y}\in C^{\perp},\ \Sigma y\equiv2-\operatorname{wt}\bar{y}\}\pmod4 E = { 2 y : y ˉ ∈ 1 + C , Σ y ≡ − wt y ˉ } , O = { 1 + 2 y : y ˉ ∈ C ⊥ , Σ y ≡ 2 − wt y ˉ } ( mod 4 )
(take y = − b ~ + 2 c ~ y=-\tilde{b}+2\tilde{c} y = − b ~ + 2 c ~ , resp. − a ~ + 2 c ~ -\tilde{a}+2\tilde{c} − a ~ + 2 c ~ , and note that wt c \operatorname{wt}c wt c is even, resp. odd, exactly when Σ y ≡ − wt b \Sigma y\equiv-\operatorname{wt}b Σ y ≡ − wt b , resp. 2 − wt a 2-\operatorname{wt}a 2 − wt a ).
Lemma (periods and sizes)
( a ) (a) ( a ) Γ + L ′ = Γ \Gamma+L'=\Gamma Γ + L ′ = Γ and L ′ ⊆ A L'\subseteq A L ′ ⊆ A . ( b ) (b) ( b ) ∣ L ′ / 8 Z n ∣ = 2 n − 1 + h |L'/8\mathbb{Z}^n|=2^{n-1+h} ∣ L ′ /8 Z n ∣ = 2 n − 1 + h and ∣ S ∣ = 2 r + 1 |S|=2^{r+1} ∣ S ∣ = 2 r + 1 . ( c ) (c) ( c ) Let L ′ ⊥ = { y ∈ ( Z / 8 ) n : χ y = 1 on L ′ } L'^\perp=\{y\in(\mathbb{Z}/8)^n:\chi_y=1\text{ on }L'\} L ′ ⊥ = { y ∈ ( Z /8 ) n : χ y = 1 on L ′ } . Then
L ′ ⊥ = { p 1 + 2 z : p ∈ { 0 , 1 } , z ∈ ( Z / 4 ) n , z ˉ ⋅ x = p λ ( x ) ∀ x ∈ R } , ∣ L ′ ⊥ ∣ = 2 2 n + 1 − h . L'^\perp=\{p\mathbf{1}+2z:p\in\{0,1\},\ z\in(\mathbb{Z}/4)^n,\ \bar z\cdot x=p\lambda(x)\ \forall x\in R\},\qquad|L'^\perp|=2^{2n+1-h}. L ′ ⊥ = { p 1 + 2 z : p ∈ { 0 , 1 } , z ∈ ( Z /4 ) n , z ˉ ⋅ x = p λ ( x ) ∀ x ∈ R } , ∣ L ′ ⊥ ∣ = 2 2 n + 1 − h .
Proof. ( a ) (a) ( a ) The lattice 8 Z n 8\mathbb{Z}^n 8 Z n fixes Γ \Gamma Γ by definition. Adding 4 ( e 1 + e j ) 4(e_1+e_j) 4 ( e 1 + e j ) to − 2 b ~ + 4 c ~ -2\widetilde b+4\widetilde c − 2 b + 4 c gives − 2 b ~ + 4 ( c + e 1 + e j ) -2\widetilde b+4(c+e_1+e_j) − 2 b + 4 ( c + e 1 + e j ) mod 8, and e 1 + e j e_1+e_j e 1 + e j has even weight, so the parity of wt c \operatorname{wt}c wt c is kept; the same holds on O O O . Let x ∈ R x\in R x ∈ R . Coordinatewise one checks − 2 b ~ + 2 x ~ ≡ − 2 ( b + x ~ ) + 4 ( x ∧ ¬ b ) -2\widetilde b+2\widetilde x\equiv-2(\widetilde{b+x})+4(x\wedge\neg b) − 2 b + 2 x ≡ − 2 ( b + x ) + 4 ( x ∧ ¬ b ) (mod 8). Hence adding 2 x ~ 2\widetilde x 2 x to a point of E E E replaces b b b by b + x b+x b + x and c c c by c + x ∧ ¬ b c+x\wedge\neg b c + x ∧ ¬ b . Here b + x ∈ 1 + C b+x\in\mathbf{1}+C b + x ∈ 1 + C because x ∈ C x\in C x ∈ C . Moreover wt ( x ∧ ¬ b ) = wt x − ∣ x ∩ b ∣ \operatorname{wt}(x\wedge\neg b)=\operatorname{wt}x-|x\cap b| wt ( x ∧ ¬ b ) = wt x − ∣ x ∩ b ∣ is even, because wt x \operatorname{wt}x wt x is even and ∣ x ∩ b ∣ ≡ x ⋅ b = x ⋅ 1 + x ⋅ ( b + 1 ) = 0 |x\cap b|\equiv x\cdot b=x\cdot\mathbf{1}+x\cdot(b+\mathbf{1})=0 ∣ x ∩ b ∣ ≡ x ⋅ b = x ⋅ 1 + x ⋅ ( b + 1 ) = 0 (as x ∈ C ⊥ x\in C^\perp x ∈ C ⊥ and b + 1 ∈ C b+\mathbf{1}\in C b + 1 ∈ C ). On O O O : 1 − 2 a ~ + 2 x ~ ≡ 1 − 2 ( a + x ~ ) + 4 ( x ∧ ¬ a ) \mathbf{1}-2\widetilde a+2\widetilde x\equiv\mathbf{1}-2(\widetilde{a+x})+4(x\wedge\neg a) 1 − 2 a + 2 x ≡ 1 − 2 ( a + x ) + 4 ( x ∧ ¬ a ) with a + x ∈ C ⊥ a+x\in C^\perp a + x ∈ C ⊥ (x ∈ R ⊆ C ⊥ x\in R\subseteq C^\perp x ∈ R ⊆ C ⊥ ), and x ∧ ¬ a x\wedge\neg a x ∧ ¬ a has even weight since x ⋅ a = 0 x\cdot a=0 x ⋅ a = 0 (x ∈ C x\in C x ∈ C ). So each generator of L ′ L' L ′ maps Γ \Gamma Γ into Γ \Gamma Γ ; as translation is injective and Γ 8 \Gamma_8 Γ 8 is finite, Γ + g = Γ \Gamma+g=\Gamma Γ + g = Γ for each generator g g g , hence Γ + L ′ = Γ \Gamma+L'=\Gamma Γ + L ′ = Γ . Then every g ∈ L ′ g\in L' g ∈ L ′ is a difference of two points of Γ \Gamma Γ , so L ′ ⊆ A L'\subseteq A L ′ ⊆ A , H ′ = A / L ′ H'=A/L' H ′ = A / L ′ is defined, and S = ( Γ − x 0 ) / L ′ ⊆ H ′ S=(\Gamma-x_0)/L'\subseteq H' S = ( Γ − x 0 ) / L ′ ⊆ H ′ .
( c ) (c) ( c ) χ y \chi_y χ y is trivial on 8 e i 8e_i 8 e i for every y y y . It is trivial on 4 ( e 1 + e j ) 4(e_1+e_j) 4 ( e 1 + e j ) iff y 1 ≡ y j ( m o d 2 ) y_1\equiv y_j\pmod2 y 1 ≡ y j ( mod 2 ) ; so y ≡ p 1 ( m o d 2 ) y\equiv p\mathbf{1}\pmod2 y ≡ p 1 ( mod 2 ) for some p ∈ { 0 , 1 } p\in\{0,1\} p ∈ { 0 , 1 } , that is y = p 1 + 2 z y=p\mathbf{1}+2z y = p 1 + 2 z . It is trivial on 2 x ~ 2\widetilde x 2 x (x ∈ R x\in R x ∈ R ) iff ∑ i ∈ x y i ≡ 0 ( m o d 4 ) \sum_{i\in x}y_i\equiv0\pmod4 ∑ i ∈ x y i ≡ 0 ( mod 4 ) . Now ∑ i ∈ x y i = p wt x + 2 ∑ i ∈ x z i ≡ 2 p λ ( x ) + 2 z ˉ ⋅ x ( m o d 4 ) \sum_{i\in x}y_i=p\operatorname{wt}x+2\sum_{i\in x}z_i\equiv2p\lambda(x)+2\bar z\cdot x\pmod4 ∑ i ∈ x y i = p wt x + 2 ∑ i ∈ x z i ≡ 2 p λ ( x ) + 2 z ˉ ⋅ x ( mod 4 ) by (F2), which vanishes iff z ˉ ⋅ x = p λ ( x ) \bar z\cdot x=p\lambda(x) z ˉ ⋅ x = p λ ( x ) . Both sides are linear in x x x , so it suffices to impose the condition on a basis of R R R : h h h independent affine conditions on z ˉ \bar z z ˉ . This leaves 2 n − h 2^{n-h} 2 n − h words z ˉ \bar z z ˉ , each with 2 n 2^n 2 n lifts to ( Z / 4 ) n (\mathbb{Z}/4)^n ( Z /4 ) n , for each p p p ; hence ∣ L ′ ⊥ ∣ = 2 ⋅ 2 n − h ⋅ 2 n |L'^\perp|=2\cdot2^{n-h}\cdot2^n ∣ L ′ ⊥ ∣ = 2 ⋅ 2 n − h ⋅ 2 n .
( b ) (b) ( b ) The characters of ( Z / 8 ) n (\mathbb{Z}/8)^n ( Z /8 ) n trivial on the subgroup L ′ / 8 Z n L'/8\mathbb{Z}^n L ′ /8 Z n form a group of order 8 n / ∣ L ′ / 8 Z n ∣ 8^n/|L'/8\mathbb{Z}^n| 8 n /∣ L ′ /8 Z n ∣ ; so ∣ L ′ / 8 Z n ∣ = 2 3 n − ( 2 n + 1 − h ) = 2 n − 1 + h |L'/8\mathbb{Z}^n|=2^{3n-(2n+1-h)}=2^{n-1+h} ∣ L ′ /8 Z n ∣ = 2 3 n − ( 2 n + 1 − h ) = 2 n − 1 + h . The set Γ 8 \Gamma_8 Γ 8 is a union of cosets of L ′ / 8 Z n L'/8\mathbb{Z}^n L ′ /8 Z n , and S S S is the set of these cosets: ∣ S ∣ = 2 n + k / 2 / 2 n − 1 + h = 2 k − h + 1 = 2 r + 1 |S|=2^{n+k/2}/2^{n-1+h}=2^{k-h+1}=2^{r+1} ∣ S ∣ = 2 n + k /2 / 2 n − 1 + h = 2 k − h + 1 = 2 r + 1 . □ \square □
Lemma (the two halves; even characters)
For y ∈ Z n y\in\mathbb{Z}^n y ∈ Z n , S ^ 8 ( y ) = 0 \widehat S_8(y)=0 S 8 ( y ) = 0 unless y ˉ ∈ { 0 , 1 } \bar y\in\{0,1\} y ˉ ∈ { 0 , 1 } , and S ^ 8 ( y ) = 0 \widehat S_8(y)=0 S 8 ( y ) = 0 for y ∉ L ′ ⊥ y\notin L'^\perp y ∈ / L ′ ⊥ . For y = 2 z y=2z y = 2 z (write z 0 = z ˉ z_0=\bar z z 0 = z ˉ ):
S ^ 8 ( 2 z ) = 2 n − 1 + k ( ( − 1 ) wt z 0 [ z 0 ∈ C ⊥ ] + i Σ z [ z 0 ∈ C ] ) . (6) \widehat S_8(2z)=2^{n-1+k}\left((-1)^{\operatorname{wt}z_0}[z_0\in C^\perp]+i^{\Sigma z}[z_0\in C]\right). \tag*{(6)} S 8 ( 2 z ) = 2 n − 1 + k ( ( − 1 ) wt z 0 [ z 0 ∈ C ⊥ ] + i Σ z [ z 0 ∈ C ] ) . (6)
Proof. On the two halves, χ y ( − 2 b ~ + 4 c ~ ) = i − ⟨ b ~ , y ⟩ ( − 1 ) c ⋅ y \chi_y(-2\widetilde b+4\widetilde c)=i^{-\langle\widetilde b,y\rangle}(-1)^{c\cdot y} χ y ( − 2 b + 4 c ) = i − ⟨ b , y ⟩ ( − 1 ) c ⋅ y and χ y ( 1 − 2 a ~ + 4 c ~ ) = ζ − ∑ y i a i ~ ( − 1 ) c ⋅ y \chi_y(1-2\widetilde a+4\widetilde c)=\zeta^{-\sum y_i\widetilde{a_i}}(-1)^{c\cdot y} χ y ( 1 − 2 a + 4 c ) = ζ − ∑ y i a i ( − 1 ) c ⋅ y . Summing over all c c c gives 2 n [ y ˉ = 0 ] 2^n[\bar y=0] 2 n [ y ˉ = 0 ] , and summing ( − 1 ) wt c + c ⋅ y (-1)^{\operatorname{wt}c+c\cdot y} ( − 1 ) wt c + c ⋅ y gives 2 n [ y ˉ = 1 ] 2^n[\bar y=1] 2 n [ y ˉ = 1 ] . Hence
∑ wt c e v e n ( − 1 ) c ⋅ y = 2 n − 1 ( [ y ˉ = 0 ] + [ y ˉ = 1 ] ) , ∑ wt c o d d ( − 1 ) c ⋅ y = 2 n − 1 ( [ y ˉ = 0 ] − [ y ˉ = 1 ] ) . \sum_{\operatorname{wt}c\ \mathrm{even}}(-1)^{c\cdot y}=2^{n-1}([\bar y=0]+[\bar y=1]),
\qquad
\sum_{\operatorname{wt}c\ \mathrm{odd}}(-1)^{c\cdot y}=2^{n-1}([\bar y=0]-[\bar y=1]). wt c even ∑ ( − 1 ) c ⋅ y = 2 n − 1 ([ y ˉ = 0 ] + [ y ˉ = 1 ]) , wt c odd ∑ ( − 1 ) c ⋅ y = 2 n − 1 ([ y ˉ = 0 ] − [ y ˉ = 1 ]) .
So S ^ 8 ( y ) = 0 \widehat S_8(y)=0 S 8 ( y ) = 0 unless y ˉ ∈ { 0 , 1 } \bar y\in\{0,1\} y ˉ ∈ { 0 , 1 } . Since Γ 8 \Gamma_8 Γ 8 is L ′ L' L ′ -periodic (Lemma 3.1), S ^ 8 ( y ) = χ y ( g ) S ^ 8 ( y ) \widehat S_8(y)=\chi_y(g)\widehat S_8(y) S 8 ( y ) = χ y ( g ) S 8 ( y ) for g ∈ L ′ g\in L' g ∈ L ′ , so S ^ 8 \widehat S_8 S 8 vanishes off L ′ ⊥ L'^\perp L ′ ⊥ . For y = 2 z y=2z y = 2 z we have i − ⟨ 2 z ~ , b ~ ⟩ = ( − 1 ) b ⋅ z 0 i^{-\langle2\widetilde z,\widetilde b\rangle}=(-1)^{b\cdot z_0} i − ⟨ 2 z , b ⟩ = ( − 1 ) b ⋅ z 0 and ζ Σ z = i Σ z \zeta^{\Sigma z}=i^{\Sigma z} ζ Σ z = i Σ z ; the even half contributes 2 n − 1 ∑ b ∈ 1 + C ( − 1 ) b ⋅ z 0 = 2 n − 1 + k ( − 1 ) wt z 0 [ z 0 ∈ C ⊥ ] 2^{n-1}\sum_{b\in\mathbf{1}+C}(-1)^{b\cdot z_0}=2^{n-1+k}(-1)^{\operatorname{wt}z_0}[z_0\in C^\perp] 2 n − 1 ∑ b ∈ 1 + C ( − 1 ) b ⋅ z 0 = 2 n − 1 + k ( − 1 ) wt z 0 [ z 0 ∈ C ⊥ ] , and the odd half 2 n − 1 i Σ z ∑ a ∈ C ⊥ ( − 1 ) a ⋅ z 0 = 2 n − 1 + k i Σ z [ z 0 ∈ C ] 2^{n-1}i^{\Sigma z}\sum_{a\in C^\perp}(-1)^{a\cdot z_0}=2^{n-1+k}i^{\Sigma z}[z_0\in C] 2 n − 1 i Σ z ∑ a ∈ C ⊥ ( − 1 ) a ⋅ z 0 = 2 n − 1 + k i Σ z [ z 0 ∈ C ] . □ \square □
Lemma (Gauss sums of the weight form)
For a binary linear code K K K and v ∈ F 2 n v\in\mathbb{F}_2^n v ∈ F 2 n put G K ( v ) = ∑ c ∈ K i wt c ( − 1 ) c ⋅ v G_K(v)=\sum_{c\in K}i^{\operatorname{wt}c}(-1)^{c\cdot v} G K ( v ) = ∑ c ∈ K i wt c ( − 1 ) c ⋅ v .
Then ∣ G K ( v ) ∣ 2 = ∣ K ∣ ∑ ρ ∈ K ∩ K ⊥ ( − 1 ) λ ( ρ ) + ρ ⋅ v |G_K(v)|^2=|K|\sum_{\rho\in K\cap K^\perp}(-1)^{\lambda(\rho)+\rho\cdot v} ∣ G K ( v ) ∣ 2 = ∣ K ∣ ∑ ρ ∈ K ∩ K ⊥ ( − 1 ) λ ( ρ ) + ρ ⋅ v . In particular ∣ G K ( v ) ∣ 2 = ∣ K ∣ 2 dim ( K ∩ K ⊥ ) [ v ⋅ ρ = λ ( ρ ) ∀ ρ ∈ K ∩ K ⊥ ] |G_K(v)|^2=|K|2^{\dim(K\cap K^\perp)}[v\cdot\rho=\lambda(\rho)\ \forall\rho\in K\cap K^\perp] ∣ G K ( v ) ∣ 2 = ∣ K ∣ 2 d i m ( K ∩ K ⊥ ) [ v ⋅ ρ = λ ( ρ ) ∀ ρ ∈ K ∩ K ⊥ ] . Proof. Write ∣ G K ( v ) ∣ 2 = ∑ c , c ′ ∈ K i wt c − wt c ′ ( − 1 ) ( c + c ′ ) ⋅ v |G_K(v)|^2=\sum_{c,c'\in K}i^{\operatorname{wt}c-\operatorname{wt}c'}(-1)^{(c+c')\cdot v} ∣ G K ( v ) ∣ 2 = ∑ c , c ′ ∈ K i wt c − wt c ′ ( − 1 ) ( c + c ′ ) ⋅ v and put c ′ = c + e c'=c+e c ′ = c + e , e ∈ K e\in K e ∈ K . By (F1), i wt c − wt c ′ = i − wt e ( − 1 ) c ⋅ e i^{\operatorname{wt}c-\operatorname{wt}c'}=i^{-\operatorname{wt}e}(-1)^{c\cdot e} i wt c − wt c ′ = i − wt e ( − 1 ) c ⋅ e . So ∣ G K ( v ) ∣ 2 = ∑ e ∈ K i − wt e ( − 1 ) e ⋅ v ∑ c ∈ K ( − 1 ) c ⋅ e |G_K(v)|^2=\sum_{e\in K}i^{-\operatorname{wt}e}(-1)^{e\cdot v}\sum_{c\in K}(-1)^{c\cdot e} ∣ G K ( v ) ∣ 2 = ∑ e ∈ K i − wt e ( − 1 ) e ⋅ v ∑ c ∈ K ( − 1 ) c ⋅ e , and the inner sum is ∣ K ∣ [ e ∈ K ⊥ ] |K|[e\in K^\perp] ∣ K ∣ [ e ∈ K ⊥ ] . For e ∈ K ∩ K ⊥ e\in K\cap K^\perp e ∈ K ∩ K ⊥ , wt e ≡ 2 λ ( e ) ( m o d 4 ) \operatorname{wt}e\equiv2\lambda(e)\pmod4 wt e ≡ 2 λ ( e ) ( mod 4 ) (F2), so i − wt e = ( − 1 ) λ ( e ) i^{-\operatorname{wt}e}=(-1)^{\lambda(e)} i − wt e = ( − 1 ) λ ( e ) . The map e ↦ λ ( e ) + e ⋅ v e\mapsto\lambda(e)+e\cdot v e ↦ λ ( e ) + e ⋅ v is linear on K ∩ K ⊥ K\cap K^\perp K ∩ K ⊥ , so the character sum equals ∣ K ∩ K ⊥ ∣ |K\cap K^\perp| ∣ K ∩ K ⊥ ∣ if it vanishes identically and 0 0 0 otherwise. □
For K = C K=C K = C and K = C ⊥ K=C^\perp K = C ⊥ the intersection K ∩ K ⊥ K\cap K^\perp K ∩ K ⊥ is R R R .
Lemma (Poisson relation)
If ∣ C ∣ = 2 n / 2 |C|=2^{n/2} ∣ C ∣ = 2 n /2 , then G C ( v ) = ζ n i − wt v G C ⊥ ( v ) ‾ G_C(v)=\zeta^n i^{-\operatorname{wt}v}\overline{G_{C^\perp}(v)} G C ( v ) = ζ n i − wt v G C ⊥ ( v ) for every v ∈ F 2 n v\in\mathbb{F}_2^n v ∈ F 2 n .
Proof. Poisson summation on F 2 n \mathbb{F}_2^n F 2 n reads ∑ c ∈ C f ( c ) = ∣ C ∣ 2 − n ∑ e ∈ C ⊥ f ^ ( e ) \sum_{c\in C}f(c)=|C|2^{-n}\sum_{e\in C^\perp}\widehat{f}(e) ∑ c ∈ C f ( c ) = ∣ C ∣ 2 − n ∑ e ∈ C ⊥ f ( e ) with f ^ ( e ) = ∑ x f ( x ) ( − 1 ) x ⋅ e \widehat{f}(e)=\sum_x f(x)(-1)^{x\cdot e} f ( e ) = ∑ x f ( x ) ( − 1 ) x ⋅ e . For f ( x ) = i wt x ( − 1 ) x ⋅ v f(x)=i^{\operatorname{wt}x}(-1)^{x\cdot v} f ( x ) = i wt x ( − 1 ) x ⋅ v ,
f ^ ( e ) = ∏ j = 1 n ( 1 + i ( − 1 ) v j + e j ) = ( 1 + i ) n ( − i ) wt ( v + e ) , \widehat{f}(e)=\prod_{j=1}^{n}\left(1+i(-1)^{v_j+e_j}\right)=(1+i)^n(-i)^{\operatorname{wt}(v+e)}, f ( e ) = j = 1 ∏ n ( 1 + i ( − 1 ) v j + e j ) = ( 1 + i ) n ( − i ) wt ( v + e ) ,
because 1 + i = 2 ζ 1+i=\sqrt{2}\zeta 1 + i = 2 ζ and 1 − i = ( 1 + i ) ( − i ) 1-i=(1+i)(-i) 1 − i = ( 1 + i ) ( − i ) . Here ( 1 + i ) n = 2 n / 2 ζ n (1+i)^n=2^{n/2}\zeta^n ( 1 + i ) n = 2 n /2 ζ n and ∣ C ∣ 2 − n = 2 − n / 2 |C|2^{-n}=2^{-n/2} ∣ C ∣ 2 − n = 2 − n /2 , so G C ( v ) = ζ n ∑ e ∈ C ⊥ i − wt ( v + e ) G_C(v)=\zeta^n\sum_{e\in C^\perp}i^{-\operatorname{wt}(v+e)} G C ( v ) = ζ n ∑ e ∈ C ⊥ i − wt ( v + e ) . By (F1), i − wt ( v + e ) = i − wt v i − wt e ( − 1 ) v ⋅ e i^{-\operatorname{wt}(v+e)}=i^{-\operatorname{wt}v}i^{-\operatorname{wt}e}(-1)^{v\cdot e} i − wt ( v + e ) = i − wt v i − wt e ( − 1 ) v ⋅ e , and ∑ e ∈ C ⊥ i − wt e ( − 1 ) e ⋅ v = G C ⊥ ( v ) ‾ \sum_{e\in C^\perp}i^{-\operatorname{wt}e}(-1)^{e\cdot v}=\overline{G_{C^\perp}(v)} ∑ e ∈ C ⊥ i − wt e ( − 1 ) e ⋅ v = G C ⊥ ( v ) . □
Lemma (odd characters)
Let y = 1 + 2 z y=1+2z y = 1 + 2 z with z ∈ ( Z / 4 ) n z\in(\mathbb{Z}/4)^n z ∈ ( Z /4 ) n , z 0 = z ‾ z_0=\overline{z} z 0 = z , z = z 0 + 2 z 1 z=z_0+2z_1 z = z 0 + 2 z 1 digitwise, and G ′ = G C ⊥ ( z 0 ) G' =G_{C^\perp}(z_0) G ′ = G C ⊥ ( z 0 ) . Then
S ^ 8 ( 1 + 2 z ) = 2 n − 1 ζ − n i wt z 0 G ′ ‾ ( 1 − ( − 1 ) k + wt z 1 ) . (7) \widehat{S}_8(1+2z)=2^{n-1}\zeta^{-n}i^{\operatorname{wt}z_0}\overline{G'}\left(1-(-1)^{k+\operatorname{wt}z_1}\right). \tag*{(7)} S 8 ( 1 + 2 z ) = 2 n − 1 ζ − n i wt z 0 G ′ ( 1 − ( − 1 ) k + wt z 1 ) . (7)
If moreover 1 + 2 z ∈ L ′ ⊥ 1+2z\in L'^\perp 1 + 2 z ∈ L ′ ⊥ , then
∣ S ^ 8 ( 1 + 2 z ) ∣ 2 = 2 2 n + k + h [ wt z 1 ≡ n / 2 + 1 ( m o d 2 ) ] . (8) |\widehat{S}_8(1+2z)|^2=2^{2n+k+h}\left[\operatorname{wt}z_1\equiv n/2+1\pmod2\right]. \tag*{(8)} ∣ S 8 ( 1 + 2 z ) ∣ 2 = 2 2 n + k + h [ wt z 1 ≡ n /2 + 1 ( mod 2 ) ] . (8)
Proof. Let E ^ \widehat{E} E and O ^ \widehat{O} O be the contributions of E E E and O O O . Here y ‾ = 1 \overline{y}=1 y = 1 , so by Lemma 3.2 the sum over c c c is + 2 n − 1 +2^{n-1} + 2 n − 1 on E E E and − 2 n − 1 -2^{n-1} − 2 n − 1 on O O O . We have ⟨ b ~ , y ⟩ = wt b + 2 ⟨ b ~ , z ⟩ ≡ wt b + 2 b ⋅ z 0 ( m o d 4 ) \langle\widetilde{b},y\rangle=\operatorname{wt}b+2\langle\widetilde{b},z\rangle\equiv\operatorname{wt}b+2b\cdot z_0\pmod4 ⟨ b , y ⟩ = wt b + 2 ⟨ b , z ⟩ ≡ wt b + 2 b ⋅ z 0 ( mod 4 ) . For b = 1 + p b=1+p b = 1 + p , p ∈ C p\in C p ∈ C : wt b = n − wt p \operatorname{wt}b=n-\operatorname{wt}p wt b = n − wt p and b ⋅ z 0 = wt z 0 + p ⋅ z 0 b\cdot z_0=\operatorname{wt}z_0+p\cdot z_0 b ⋅ z 0 = wt z 0 + p ⋅ z 0 . Therefore
E ^ = 2 n − 1 i − n ( − 1 ) wt z 0 G C ( z 0 ) , O ^ = − 2 n − 1 ζ Σ y G ′ , Σ y = n + 2 Σ z . \widehat{E}=2^{n-1}i^{-n}(-1)^{\operatorname{wt}z_0}G_C(z_0),\qquad\widehat{O}=-2^{n-1}\zeta^{\Sigma_y}G',\qquad\Sigma_y=n+2\Sigma_z. E = 2 n − 1 i − n ( − 1 ) wt z 0 G C ( z 0 ) , O = − 2 n − 1 ζ Σ y G ′ , Σ y = n + 2 Σ z .
By Lemma 3.4 (here ∣ C ∣ = 2 n / 2 |C|=2^{n/2} ∣ C ∣ = 2 n /2 is used), G C ( z 0 ) = ζ n i − wt z 0 G ′ ‾ G_C(z_0)=\zeta^n i^{-\operatorname{wt}z_0}\overline{G'} G C ( z 0 ) = ζ n i − wt z 0 G ′ , with i − n ζ n = ζ − n i^{-n}\zeta^n=\zeta^{-n} i − n ζ n = ζ − n and ( − 1 ) wt z 0 i − wt z 0 = i wt z 0 (-1)^{\operatorname{wt}z_0}i^{-\operatorname{wt}z_0}=i^{\operatorname{wt}z_0} ( − 1 ) wt z 0 i − wt z 0 = i wt z 0 this gives E ^ = 2 n − 1 ζ − n i wt z 0 G ′ ‾ \widehat{E}=2^{n-1}\zeta^{-n}i^{\operatorname{wt}z_0}\overline{G'} E = 2 n − 1 ζ − n i wt z 0 G ′ . Also ζ Σ y = ζ n i Σ z \zeta^{\Sigma_y}=\zeta^n i^{\Sigma_z} ζ Σ y = ζ n i Σ z , so
O ^ / E ^ = − ζ 2 n i Σ z − wt z 0 = − i n i 2 wt z 1 = − ( − 1 ) k + wt z 1 (when E ^ ≠ 0 ) . \widehat{O}/\widehat{E}=-\zeta^{2n}i^{\Sigma_z-\operatorname{wt}z_0}=-i^n i^{2\operatorname{wt}z_1}=-(-1)^{k+\operatorname{wt}z_1}\qquad\text{(when }\widehat{E}\ne0\text{)}. O / E = − ζ 2 n i Σ z − wt z 0 = − i n i 2 wt z 1 = − ( − 1 ) k + wt z 1 (when E = 0 ) .
So S ^ 8 = E ^ + O ^ = E ^ ( 1 − ( − 1 ) k + wt z 1 ) \widehat{S}_8=\widehat{E}+\widehat{O}=\widehat{E}(1-(-1)^{k+\operatorname{wt}z_1}) S 8 = E + O = E ( 1 − ( − 1 ) k + wt z 1 ) , which is (3.5.1). Hence S ^ 8 \widehat{S}_8 S 8 is either 0 0 0 or 2 E ^ 2\widehat{E} 2 E , according as wt z 1 ≡ k \operatorname{wt}z_1\equiv k wt z 1 ≡ k or k + 1 k+1 k + 1 . If 1 + 2 z ∈ L ′ ⊥ 1+2z\in L'^\perp 1 + 2 z ∈ L ′ ⊥ then z 0 ⋅ x = λ ( x ) z_0\cdot x=\lambda(x) z 0 ⋅ x = λ ( x ) for all x ∈ R x\in R x ∈ R (Lemma 3.1, p = 1 p=1 p = 1 ), and Lemma 3.3 with K = C ⊥ K=C^\perp K = C ⊥ gives ∣ G ′ ∣ 2 = 2 2 k + 2 h |G'|^2=2^{2k+2h} ∣ G ′ ∣ 2 = 2 2 k + 2 h . Then ∣ S ^ 8 ∣ 2 = 4 ⋅ 2 2 n − 2 ⋅ 2 k + h |\widehat{S}_8|^2=4\cdot2^{2n-2}\cdot2^{k+h} ∣ S 8 ∣ 2 = 4 ⋅ 2 2 n − 2 ⋅ 2 k + h in the second case (wt z 1 ≡ k + 1 \operatorname{wt}z_1\equiv k+1 wt z 1 ≡ k + 1 ), and 0 0 0 in the first, which is (3.5.2) since k = n / 2 k=n/2 k = n /2 . □
Lemma (the dual group)
(a) Every character of H ′ = A / L ′ H^\prime=A/L^\prime H ′ = A / L ′ is χ y ∣ A \chi_y|_A χ y ∣ A for some y ∈ L ′ ⊥ y\in L^{\prime\perp} y ∈ L ′ ⊥ , and χ y = χ y ′ \chi_y=\chi_{y^\prime} χ y = χ y ′ on H ′ H^\prime H ′ iff y − y ′ ∈ A ⊥ : = { y : χ y = 1 on A } y-y^\prime\in A^\perp:=\{y:\chi_y=1\text{ on }A\} y − y ′ ∈ A ⊥ := { y : χ y = 1 on A } . So H ′ ^ ≅ L ′ ⊥ / A ⊥ \widehat{H^\prime}\cong L^{\prime\perp}/A^\perp H ′ ≅ L ′ ⊥ / A ⊥ . (b) A ⊥ = { 2 z : z ∈ ( Z / 4 ) n , z ˉ ∈ R , ∑ z i ≡ 0 ( m o d 4 ) } A^\perp=\{2z:z\in(\mathbb{Z}/4)^n,\ \bar z\in R,\ \sum z_i\equiv0\pmod4\} A ⊥ = { 2 z : z ∈ ( Z /4 ) n , z ˉ ∈ R , ∑ z i ≡ 0 ( mod 4 )} . It has 2 h + n − 1 2^{h+n-1} 2 h + n − 1 elements, and ∣ H ′ ∣ = 2 2 r + 2 |H^\prime|=2^{2r+2} ∣ H ′ ∣ = 2 2 r + 2 . (c) A ∗ = 1 8 { z ∈ Z n : z m o d 2 ∈ R , ∑ z i ≡ 0 ( m o d 4 ) } A^*=\frac{1}{8}\{z\in\mathbb{Z}^n:z\bmod2\in R,\ \sum z_i\equiv0\pmod4\} A ∗ = 8 1 { z ∈ Z n : z mod 2 ∈ R , ∑ z i ≡ 0 ( mod 4 )} , which is (3). The map y / 8 + A ∗ ↦ χ y ∣ H ′ y/8+A^*\mapsto\chi_y|_{H^\prime} y /8 + A ∗ ↦ χ y ∣ H ′ is an isomorphism L ′ ∗ / A ∗ → H ′ ^ L^{\prime*}/A^*\to\widehat{H^\prime} L ′ ∗ / A ∗ → H ′ , compatible with the pairing ⟨ x + L ′ , y / 8 + A ∗ ⟩ = e 2 π i ⟨ x , y ⟩ / 8 = χ y ( x ) \langle x+L^\prime,y/8+A^*\rangle=e^{2\pi i\langle x,y\rangle/8}=\chi_y(x) ⟨ x + L ′ , y /8 + A ∗ ⟩ = e 2 π i ⟨ x , y ⟩ /8 = χ y ( x ) . (d) Let E = { 2 z ∈ L ′ ⊥ } E=\{2z\in L^{\prime\perp}\} E = { 2 z ∈ L ′ ⊥ } be the even characters, z ∈ ( Z / 4 ) n z\in(\mathbb{Z}/4)^n z ∈ ( Z /4 ) n with z ˉ ∈ R ⊥ \bar z\in R^\perp z ˉ ∈ R ⊥ . The map ψ ( 2 z ) = ( z ˉ + R , ∑ z i m o d 4 ) ∈ ( R ⊥ / R ) × Z / 4 \psi(2z)=(\bar z+R,\sum z_i\bmod4)\in(R^\perp/R)\times\mathbb{Z}/4 ψ ( 2 z ) = ( z ˉ + R , ∑ z i mod 4 ) ∈ ( R ⊥ / R ) × Z /4 is a homomorphism with kernel A ⊥ A^\perp A ⊥ and image { ( v + R , s ) : s ≡ wt v ( m o d 2 ) } \{(v+R,s):s\equiv\operatorname{wt}v\pmod2\} {( v + R , s ) : s ≡ wt v ( mod 2 )} . So ∣ E / A ⊥ ∣ = 2 2 r + 1 |E/A^\perp|=2^{2r+1} ∣ E / A ⊥ ∣ = 2 2 r + 1 , and E / A ⊥ E/A^\perp E / A ⊥ has index 2 in H ′ ^ \widehat{H^\prime} H ′ . (e) H ′ ^ \widehat{H^\prime} H ′ is elementary abelian if and only if 1 ∈ R 1\in R 1 ∈ R .
Proof. (a) A character of the subgroup A / L ′ A/L^\prime A / L ′ of the finite abelian group Z n / L ′ \mathbb{Z}^n/L^\prime Z n / L ′ extends to Z n / L ′ \mathbb{Z}^n/L^\prime Z n / L ′ . The characters of Z n / L ′ \mathbb{Z}^n/L^\prime Z n / L ′ are the χ y \chi_y χ y with y ∈ L ′ ⊥ y\in L^{\prime\perp} y ∈ L ′ ⊥ (as 8 Z n ⊆ L ′ 8\mathbb{Z}^n\subseteq L^\prime 8 Z n ⊆ L ′ ). Two such characters agree on A A A iff y − y ′ ∈ A ⊥ y-y^\prime\in A^\perp y − y ′ ∈ A ⊥ .
(b) By the triangle inequality, y ∈ A ⊥ y\in A^\perp y ∈ A ⊥ iff χ y \chi_y χ y is constant on Γ 8 \Gamma_8 Γ 8 iff ∣ S ^ 8 ( y ) ∣ = ∣ Γ 8 ∣ = 2 n + k |\widehat{S}_8(y)|=|\Gamma_8|=2^{n+k} ∣ S 8 ( y ) ∣ = ∣ Γ 8 ∣ = 2 n + k . Characters with y ˉ ∉ { 0 , 1 } \bar y\notin\{0,1\} y ˉ ∈ / { 0 , 1 } have S ^ 8 = 0 \widehat{S}_8=0 S 8 = 0 . For y ˉ = 1 \bar y=1 y ˉ = 1 , (3.5.2) and Lemma 3.2 give ∣ S ^ 8 ∣ 2 ≤ 2 2 n + k + h < 2 2 n + 2 k |\widehat{S}_8|^2\leq2^{2n+k+h}<2^{2n+2k} ∣ S 8 ∣ 2 ≤ 2 2 n + k + h < 2 2 n + 2 k , because h < k h<k h < k . For y = 2 z y=2z y = 2 z , formula (3.2.1) has modulus 2 n + h 2^{n+h} 2 n + h iff both terms are present and equal, i.e. z ∈ C ∩ C ⊥ = R z\in C\cap C^\perp=R z ∈ C ∩ C ⊥ = R and i ∑ z i = ( − 1 ) wt z ˉ = 1 i^{\sum z_i}=(-1)^{\operatorname{wt}\bar z}=1 i ∑ z i = ( − 1 ) wt z ˉ = 1 (the words of R R R are even). This is the stated set. Count: 2 h 2^h 2 h words z ˉ \bar z z ˉ , 2 n 2^n 2 n lifts, half of which satisfy ∑ z i ≡ 0 ( m o d 4 ) \sum z_i\equiv0\pmod4 ∑ z i ≡ 0 ( mod 4 ) (since wt z ˉ \operatorname{wt}\bar z wt z ˉ is even): 2 h + n − 1 2^{h+n-1} 2 h + n − 1 . Hence ∣ H ′ ∣ = ∣ L ′ ⊥ ∣ / ∣ A ⊥ ∣ = 2 2 n + 1 − h / 2 h + n − 1 = 2 n + 2 − 2 h = 2 2 r + 2 |H^\prime|=|L^{\prime\perp}|/|A^\perp|=2^{2n+1-h}/2^{h+n-1}=2^{n+2-2h}=2^{2r+2} ∣ H ′ ∣ = ∣ L ′ ⊥ ∣/∣ A ⊥ ∣ = 2 2 n + 1 − h / 2 h + n − 1 = 2 n + 2 − 2 h = 2 2 r + 2 .
(c) Since 8 Z n ⊆ L ′ ⊆ A ⊆ Z n 8\mathbb{Z}^n\subseteq L^\prime\subseteq A\subseteq\mathbb{Z}^n 8 Z n ⊆ L ′ ⊆ A ⊆ Z n , we have A ∗ ⊆ 1 8 Z n A^*\subseteq\frac{1}{8}\mathbb{Z}^n A ∗ ⊆ 8 1 Z n , and, for y ∈ Z n y\in\mathbb{Z}^n y ∈ Z n : y / 8 ∈ A ∗ y/8\in A^* y /8 ∈ A ∗ iff ⟨ a , y ⟩ ∈ 8 Z \langle a,y\rangle\in8\mathbb{Z} ⟨ a , y ⟩ ∈ 8 Z for all a ∈ A a\in A a ∈ A iff y m o d 8 ∈ A ⊥ y\bmod8\in A^\perp y mod 8 ∈ A ⊥ . By (b), A ∗ = 1 8 ⋅ 2 { z ∈ Z n : z ˉ ∈ R , ∑ z i ≡ 0 ( m o d 4 ) } A^*=\frac{1}{8}\cdot2\{z\in\mathbb{Z}^n:\bar z\in R,\ \sum z_i\equiv0\pmod4\} A ∗ = 8 1 ⋅ 2 { z ∈ Z n : z ˉ ∈ R , ∑ z i ≡ 0 ( mod 4 )} , which is (3). In the same way L ′ ∗ = 1 8 { y ∈ Z n : y m o d 8 ∈ L ′ ⊥ } L^{\prime*}=\frac{1}{8}\{y\in\mathbb{Z}^n:y\bmod8\in L^{\prime\perp}\} L ′ ∗ = 8 1 { y ∈ Z n : y mod 8 ∈ L ′ ⊥ } , and y / 8 + A ∗ ↦ ( y m o d 8 ) + A ⊥ y/8+A^*\mapsto(y\bmod8)+A^\perp y /8 + A ∗ ↦ ( y mod 8 ) + A ⊥ is an isomorphism L ′ ∗ / A ∗ → L ′ ⊥ / A ⊥ ≅ H ′ ^ L^{\prime*}/A^*\to L^{\prime\perp}/A^\perp\cong\widehat{H^\prime} L ′ ∗ / A ∗ → L ′ ⊥ / A ⊥ ≅ H ′ that matches the pairing.
(d) ψ \psi ψ is a homomorphism because z ↦ z ˉ z\mapsto\bar z z ↦ z ˉ and z ↦ ∑ z i m o d 4 z\mapsto\sum z_i\bmod4 z ↦ ∑ z i mod 4 are additive. Its kernel is { z ˉ ∈ R , ∑ z i ≡ 0 } = A ⊥ \{\bar z\in R,\ \sum z_i\equiv0\}=A^\perp { z ˉ ∈ R , ∑ z i ≡ 0 } = A ⊥ by (b). Since ∑ z i ≡ wt z ˉ ( m o d 2 ) \sum z_i\equiv\operatorname{wt}\bar z\pmod2 ∑ z i ≡ wt z ˉ ( mod 2 ) , the image lies in { ( v + R , s ) : s ≡ wt v } \{(v+R,s):s\equiv\operatorname{wt}v\} {( v + R , s ) : s ≡ wt v } (well defined because R R R is even). Conversely, for such ( v + R , s ) (v+R,s) ( v + R , s ) take z = v ~ + 2 t ~ z=\tilde v+2\tilde t z = v ~ + 2 t ~ with wt v + 2 wt t ≡ s ( m o d 4 ) \operatorname{wt}v+2\operatorname{wt}t\equiv s\pmod4 wt v + 2 wt t ≡ s ( mod 4 ) . The image has 2 n − 2 h ⋅ 2 = 2 2 r + 1 2^{n-2h}\cdot2=2^{2r+1} 2 n − 2 h ⋅ 2 = 2 2 r + 1 elements (n − 2 h = 2 r n-2h=2r n − 2 h = 2 r ). The even characters are those with p = 0 p=0 p = 0 in Lemma 3.1(c), which is a subgroup of index 2 of L ′ ⊥ L^{\prime\perp} L ′ ⊥ .
(e) We ask whether 2 y ∈ A ⊥ 2y\in A^\perp 2 y ∈ A ⊥ for every y ∈ L ′ ⊥ y\in L^{\prime\perp} y ∈ L ′ ⊥ . Suppose 1 ∈ R 1\in R 1 ∈ R . For y = 2 z y=2z y = 2 z with z ˉ ∈ R ⊥ \bar z\in R^\perp z ˉ ∈ R ⊥ : 2 y = 2 z ′ 2y=2z^\prime 2 y = 2 z ′ with z ′ = 2 z z^\prime=2z z ′ = 2 z , z ˉ ′ = 0 \bar z^\prime=0 z ˉ ′ = 0 , and ∑ z i ′ = 2 ∑ z i ≡ 2 wt z ˉ ≡ 0 \sum z_i^\prime=2\sum z_i\equiv2\operatorname{wt}\bar z\equiv0 ∑ z i ′ = 2 ∑ z i ≡ 2 wt z ˉ ≡ 0 since z ˉ ⊥ 1 \bar z\perp1 z ˉ ⊥ 1 . For y = 1 + 2 z y=1+2z y = 1 + 2 z : 2 y = 2 z ′ 2y=2z^\prime 2 y = 2 z ′ with z ′ = 1 + 2 z z^\prime=1+2z z ′ = 1 + 2 z , so z ˉ ′ = 1 ∈ R \bar z^\prime=1\in R z ˉ ′ = 1 ∈ R , and ∑ z i ′ = n + 2 ∑ z i \sum z_i^\prime=n+2\sum z_i ∑ z i ′ = n + 2 ∑ z i . By part (d) of Lemma 3.1(c) at x = 1 x=1 x = 1 gives wt z ˉ ≡ n / 2 ( m o d 2 ) \operatorname{wt}\bar z\equiv n/2\pmod2 wt z ˉ ≡ n /2 ( mod 2 ) , so 2 ∑ z i ≡ n ( m o d 4 ) 2\sum z_i\equiv n\pmod4 2 ∑ z i ≡ n ( mod 4 ) and ∑ z i ′ ≡ 2 n ≡ 0 \sum z_i^\prime\equiv2n\equiv0 ∑ z i ′ ≡ 2 n ≡ 0 . Hence 2 y ∈ A ⊥ 2y\in A^\perp 2 y ∈ A ⊥ . Suppose 1 ∉ R 1\notin R 1 ∈ / R . As R = ( R ⊥ ) ⊥ R=(R^\perp)^\perp R = ( R ⊥ ) ⊥ , some z 0 ∈ R ⊥ z_0\in R^\perp z 0 ∈ R ⊥ has odd weight. For y = 2 z 0 ∈ E y=2z_0\in E y = 2 z 0 ∈ E : 2 y = 2 z ′ 2y=2z^\prime 2 y = 2 z ′ with z ′ = 2 z 0 z^\prime=2z_0 z ′ = 2 z 0 , z ˉ ′ = 0 \bar z^\prime=0 z ˉ ′ = 0 , ∑ z i ′ = 2 wt z 0 ≡ 2 \sum z_i^\prime=2\operatorname{wt}z_0\equiv2 ∑ z i ′ = 2 wt z 0 ≡ 2 , so 2 y ∉ A ⊥ 2y\notin A^\perp 2 y ∈ / A ⊥ : the character has order 4. □
Lemma (the target function)
Put ∣ T ∣ = 2 r + 1 |T|=2^{r+1} ∣ T ∣ = 2 r + 1 (proved in § 3.8) and, for χ = χ y \chi=\chi_y χ = χ y with y ∈ L ′ ⊥ y\in L^{\prime\perp} y ∈ L ′ ⊥ , ν ∗ ( χ ) = ∣ T ∣ ∣ S ^ H ( χ ) ∣ 2 / ∣ S ∣ 2 \nu^*(\chi)=|T||\widehat{S}_H(\chi)|^2/|S|^2 ν ∗ ( χ ) = ∣ T ∣∣ S H ( χ ) ∣ 2 /∣ S ∣ 2 , where S ^ H ( χ ) = ∑ s ∈ S χ ( s ) \widehat{S}_H(\chi)=\sum_{s\in S}\chi(s) S H ( χ ) = ∑ s ∈ S χ ( s ) . Then:
for odd y = 1 + 2 z y=1+2z y = 1 + 2 z : ν ∗ = 2 [ wt z 1 ≡ n / 2 + 1 ( m o d 2 ) ] \nu^*=2[\operatorname{wt}z_1\equiv n/2+1\pmod2] ν ∗ = 2 [ wt z 1 ≡ n /2 + 1 ( mod 2 )] ;
for even y = 2 z y=2z y = 2 z : ν ∗ = 2 r − 1 ∣ ( − 1 ) wt z ˉ [ z ˉ ∈ C ⊥ ] + i ∑ z i [ z ˉ ∈ C ] ∣ 2 \nu^*=2^{r-1}|(-1)^{\operatorname{wt}\bar z}[\bar z\in C^\perp]+i^{\sum z_i}[\bar z\in C]|^2 ν ∗ = 2 r − 1 ∣ ( − 1 ) wt z ˉ [ z ˉ ∈ C ⊥ ] + i ∑ z i [ z ˉ ∈ C ] ∣ 2 . In ψ \psi ψ -coordinates of Lemma 3.6(d): ν ∗ = 2 r + 1 \nu^*=2^{r+1} ν ∗ = 2 r + 1 at ( 0 , 0 ) (0,0) ( 0 , 0 ) ; ν ∗ = 0 \nu^*=0 ν ∗ = 0 at ( 0 , 2 ) (0,2) ( 0 , 2 ) ; ν ∗ = 2 r − 1 \nu^*=2^{r-1} ν ∗ = 2 r − 1 at the 4 ( 2 r − 1 ) 4(2^r-1) 4 ( 2 r − 1 ) classes ( v + R , s ) (v+R,s) ( v + R , s ) with v ∈ ( C ∪ C ⊥ ) ∖ R v\in(C\cup C^\perp)\setminus R v ∈ ( C ∪ C ⊥ ) ∖ R ; ν ∗ = 0 \nu^*=0 ν ∗ = 0 elsewhere.
Proof. Since χ y \chi_y χ y is trivial on L ′ L^\prime L ′ , each of the ∣ S ∣ |S| ∣ S ∣ cosets of L ′ L^\prime L ′ in Γ − x 0 \Gamma-x_0 Γ − x 0 contributes ∣ L ′ / 8 Z n ∣ |L^\prime/8\mathbb{Z}^n| ∣ L ′ /8 Z n ∣ equal terms: ∣ S ^ 8 ( y ) ∣ = ∣ L ′ / 8 Z n ∣ ∣ S ^ H ( χ y ) ∣ |\widehat{S}_8(y)|=|L^\prime/8\mathbb{Z}^n||\widehat{S}_H(\chi_y)| ∣ S 8 ( y ) ∣ = ∣ L ′ /8 Z n ∣∣ S H ( χ y ) ∣ . With ∣ S ∣ = ∣ S ∣ / ∣ L ′ / 8 Z n ∣ |S|=|S|/|L^\prime/8\mathbb{Z}^n| ∣ S ∣ = ∣ S ∣/∣ L ′ /8 Z n ∣ this gives ∣ S ^ H ∣ 2 / ∣ S ∣ 2 = ∣ S ^ 8 ∣ 2 / ∣ Γ 8 ∣ 2 |\widehat{S}_H|^2/|S|^2=|\widehat{S}_8|^2/|\Gamma_8|^2 ∣ S H ∣ 2 /∣ S ∣ 2 = ∣ S 8 ∣ 2 /∣ Γ 8 ∣ 2 . For odd y y y , (3.5.2) gives ν ∗ = 2 r + 1 2 n + k + h / 2 2 n + 2 k [ ⋯ ] = 2 r + 1 − ( k − h ) [ ⋯ ] = 2 [ ⋯ ] \nu^*=2^{r+1}2^{n+k+h}/2^{2n+2k}[\cdots]=2^{r+1-(k-h)}[\cdots]=2[\cdots] ν ∗ = 2 r + 1 2 n + k + h / 2 2 n + 2 k [ ⋯ ] = 2 r + 1 − ( k − h ) [ ⋯ ] = 2 [ ⋯ ] . For even y , y, y , (3.2.1) gives ν ∗ = 2 r + 1 ⋅ 2 2 n − 2 + 2 k / 2 2 n + 2 k ∣ ⋯ ∣ 2 = 2 r − 1 ∣ ⋯ ∣ 2 \nu^*=2^{r+1}\cdot2^{2n-2+2k}/2^{2n+2k}|\cdots|^2=2^{r-1}|\cdots|^2 ν ∗ = 2 r + 1 ⋅ 2 2 n − 2 + 2 k / 2 2 n + 2 k ∣ ⋯ ∣ 2 = 2 r − 1 ∣ ⋯ ∣ 2 . For z ˉ ∈ R \bar z\in R z ˉ ∈ R the bracket is ∣ 1 + i ∑ z ∣ 2 |1+i^{\sum z}|^2 ∣1 + i ∑ z ∣ 2 , equal to 4 4 4 if ∑ z ≡ 0 \sum z\equiv0 ∑ z ≡ 0 and to 0 0 0 if ∑ z ≡ 2 \sum z\equiv2 ∑ z ≡ 2 (∑ z \sum z ∑ z is even). For z ˉ ∈ ( C ∪ C ⊥ ) ∖ R \bar z\in(C\cup C^\perp)\setminus R z ˉ ∈ ( C ∪ C ⊥ ) ∖ R exactly one term is present and the modulus is 1 1 1 . Otherwise it is 0 0 0 . Finally R ⊥ / R = C / R ⊕ C ⊥ / R R^\perp/R=C/R\oplus C^\perp/R R ⊥ / R = C / R ⊕ C ⊥ / R (as R ⊥ = C + C ⊥ R^\perp=C+C^\perp R ⊥ = C + C ⊥ and C ∩ C ⊥ = R C\cap C^\perp=R C ∩ C ⊥ = R ); each of C / R ∖ 0 C/R\setminus0 C / R ∖ 0 and C ⊥ / R ∖ 0 C^\perp/R\setminus0 C ⊥ / R ∖ 0 has 2 r − 1 2^r-1 2 r − 1 elements, and each v v v carries two classes s ≡ wt v ( m o d 2 ) s\equiv\operatorname{wt}v\pmod2 s ≡ wt v ( mod 2 ) . □
Lemma (the set T T T )
Put a ( c ) = 2 c ~ + 4 ( u ⋅ c ) e 1 a(c)=2\tilde c+4(u\cdot c)e_1 a ( c ) = 2 c ~ + 4 ( u ⋅ c ) e 1 for c ∈ C c\in C c ∈ C , a 2 ( d ) = 2 d ~ + 4 ( u ⋅ d ) e 1 a_2(d)=2\tilde d+4(u\cdot d)e_1 a 2 ( d ) = 2 d ~ + 4 ( u ⋅ d ) e 1 for d ∈ C ⊥ d\in C^\perp d ∈ C ⊥ , and y ∗ = 1 + 2 ( u + w ) + 4 ε e 1 y^*=1+2(u+w)+4\varepsilon e_1 y ∗ = 1 + 2 ( u + w ) + 4 ε e 1 . Then T = X 1 ∪ ( y ∗ + X 2 ) T=X_1\cup(y^*+X_2) T = X 1 ∪ ( y ∗ + X 2 ) with X 1 = { a ( c ) } X_1=\{a(c)\} X 1 = { a ( c )} , X 2 = { a 2 ( d ) } X_2=\{a_2(d)\} X 2 = { a 2 ( d )} , and: (i) every element of T T T lies in L ′ ⊥ L'^\perp L ′ ⊥ ; (ii) ψ ( a ( c ) ) = ( c + R , F 1 ( c ) ) \psi(a(c))=(c+R,F_1(c)) ψ ( a ( c )) = ( c + R , F 1 ( c )) with F 1 ( c ) = wt c + 2 u ⋅ c ( m o d 4 ) F_1(c)=\operatorname{wt}c+2u\cdot c\pmod4 F 1 ( c ) = wt c + 2 u ⋅ c ( mod 4 ) , which depends only on c + R c+R c + R ; likewise ψ ( a 2 ( d ) ) = ( d + R , F 2 ( d ) ) \psi(a_2(d))=(d+R,F_2(d)) ψ ( a 2 ( d )) = ( d + R , F 2 ( d )) with F 2 ( d ) = wt d + 2 u ⋅ d F_2(d)=\operatorname{wt}d+2u\cdot d F 2 ( d ) = wt d + 2 u ⋅ d on C ⊥ / R C^\perp/R C ⊥ / R ; (iii) as a set of characters of H ′ H' H ′ , X 1 X_1 X 1 is the graph of F 1 F_1 F 1 over C / R C/R C / R and X 2 X_2 X 2 the graph of F 2 F_2 F 2 over C ⊥ / R C^\perp/R C ⊥ / R : each has 2 r 2^r 2 r elements, and each element has 2 h 2^h 2 h preimages. The two halves X 1 X_1 X 1 and y ∗ + X 2 y^*+X_2 y ∗ + X 2 are disjoint (even versus odd), so ∣ T ∣ = 2 r + 1 |T|=2^{r+1} ∣ T ∣ = 2 r + 1 .
Proof. The second half of (2) is y ∗ + a 2 ( d ) y^*+a_2(d) y ∗ + a 2 ( d ) . (i) For a ( c ) a(c) a ( c ) : z = c ~ + 2 ( u ⋅ c ) e 1 z=\tilde c+2(u\cdot c)e_1 z = c ~ + 2 ( u ⋅ c ) e 1 has z ˉ = c ∈ C ⊆ R ⊥ \bar z=c\in C\subseteq R^\perp z ˉ = c ∈ C ⊆ R ⊥ . For a 2 ( d ) a_2(d) a 2 ( d ) : z ˉ = d ∈ C ⊥ ⊆ R ⊥ \bar z=d\in C^\perp\subseteq R^\perp z ˉ = d ∈ C ⊥ ⊆ R ⊥ (as R ⊆ C R\subseteq C R ⊆ C ). For y ∗ y^* y ∗ : p = 1 p=1 p = 1 , z ˉ = u + w \bar z=u+w z ˉ = u + w , and ( u + w ) ⋅ x = λ ( x ) + 0 (u+w)\cdot x=\lambda(x)+0 ( u + w ) ⋅ x = λ ( x ) + 0 for x ∈ R x\in R x ∈ R by (F3). (ii) ∑ z = wt c + 2 u ⋅ c \sum z=\operatorname{wt}c+2u\cdot c ∑ z = wt c + 2 u ⋅ c . For x ∈ R x\in R x ∈ R and c ∈ C c\in C c ∈ C we have c ⋅ x = 0 c\cdot x=0 c ⋅ x = 0 , so by (F1), (F2): F 1 ( c + x ) = wt c + 2 λ ( x ) + 2 u ⋅ c + 2 λ ( x ) = F 1 ( c ) F_1(c+x)=\operatorname{wt}c+2\lambda(x)+2u\cdot c+2\lambda(x)=F_1(c) F 1 ( c + x ) = wt c + 2 λ ( x ) + 2 u ⋅ c + 2 λ ( x ) = F 1 ( c ) ; the same for F 2 F_2 F 2 using d ⋅ x = 0 d\cdot x=0 d ⋅ x = 0 for d ∈ C ⊥ d\in C^\perp d ∈ C ⊥ , x ∈ R ⊆ C x\in R\subseteq C x ∈ R ⊆ C . (iii) follows from (ii): ψ \psi ψ separates distinct classes c + R c+R c + R by its first coordinate, and elements with the same image differ by an element of A ⊥ A^\perp A ⊥ , hence are the same character. □
Lemma (ν T \nu_T ν T on even characters)
On E / A ⊥ E/A^\perp E / A ⊥ , ν T = ν ∗ \nu_T=\nu^* ν T = ν ∗ .
Proof. A difference of two elements of T T T is even iff both lie in the same half. So ν T = ν X 1 + ν X 2 \nu_T=\nu_{X_1}+\nu_{X_2} ν T = ν X 1 + ν X 2 on even characters (y ∗ + X 2 y^*+X_2 y ∗ + X 2 has the same differences as X 2 X_2 X 2 ). In ψ \psi ψ -coordinates X 1 = { ( c + R , F 1 ( c ) ) } X_1=\{(c+R,F_1(c))\} X 1 = {( c + R , F 1 ( c ))} . For v ∈ C / R v\in C/R v ∈ C / R , (F1) gives F 1 ( c + v ) − F 1 ( c ) = F 1 ( v ) + 2 c ⋅ v ( m o d 4 ) F_1(c+v)-F_1(c)=F_1(v)+2c\cdot v\pmod4 F 1 ( c + v ) − F 1 ( c ) = F 1 ( v ) + 2 c ⋅ v ( mod 4 ) . The form c ↦ c ⋅ v c\mapsto c\cdot v c ↦ c ⋅ v on C / R C/R C / R is well defined (v ∈ C ⊆ R ⊥ v\in C\subseteq R^\perp v ∈ C ⊆ R ⊥ ), and it is non-zero iff v ∉ R v\notin R v ∈ / R , because the radical of the dot product on C C C is C ∩ C ⊥ = R C\cap C^\perp=R C ∩ C ⊥ = R . So for v ≠ 0 v\ne0 v = 0 in C / R C/R C / R the differences ( v , F 1 ( v ) ) (v,F_1(v)) ( v , F 1 ( v )) and ( v , F 1 ( v ) + 2 ) (v,F_1(v)+2) ( v , F 1 ( v ) + 2 ) each occur 2 r − 1 2^{r-1} 2 r − 1 times; for v = 0 v=0 v = 0 the difference ( 0 , 0 ) (0,0) ( 0 , 0 ) occurs 2 r 2^r 2 r times and ( 0 , 2 ) (0,2) ( 0 , 2 ) never; no other class occurs. Thus ν X 1 = 2 r \nu_{X_1}=2^r ν X 1 = 2 r at ( 0 , 0 ) (0,0) ( 0 , 0 ) , 2 r − 1 2^{r-1} 2 r − 1 at both classes over each v ∈ C / R ∖ 0 v\in C/R\setminus0 v ∈ C / R ∖ 0 , and 0 0 0 elsewhere. The same holds for X 2 X_2 X 2 over C ⊥ / R C^\perp/R C ⊥ / R . The supports of the two halves over v ≠ 0 v\ne0 v = 0 are disjoint (C / R ∩ C ⊥ / R = 0 C/R\cap C^\perp/R=0 C / R ∩ C ⊥ / R = 0 ), so ν T \nu_T ν T is 2 r + 1 2^{r+1} 2 r + 1 at ( 0 , 0 ) (0,0) ( 0 , 0 ) , 0 0 0 at ( 0 , 2 ) (0,2) ( 0 , 2 ) , 2 r − 1 2^{r-1} 2 r − 1 over ( C ∪ C ⊥ ) ∖ R (C\cup C^\perp)\setminus R ( C ∪ C ⊥ ) ∖ R , and 0 0 0 elsewhere: this is ν ∗ \nu^* ν ∗ (Lemma 3.7). When C C C is even, F 1 ( c ) / 2 = wt ( c ) / 2 + u ⋅ c ( m o d 2 ) F_1(c)/2=\operatorname{wt}(c)/2+u\cdot c\pmod2 F 1 ( c ) /2 = wt ( c ) /2 + u ⋅ c ( mod 2 ) is a non-degenerate quadratic form on C / R C/R C / R with polar form c ⋅ c ′ c\cdot c' c ⋅ c ′ , i.e. a bent function. □
Lemma (ν T \nu_T ν T on odd characters)
For odd characters x x x , ν T ( x ) = ν ∗ ( x ) \nu_T(x)=\nu^*(x) ν T ( x ) = ν ∗ ( x ) . Moreover the odd characters with ν ∗ = 2 \nu^*=2 ν ∗ = 2 are exactly the 2 2 r 2^{2r} 2 2 r characters g ( c , d ) = y ∗ + a 2 ( d ) − a ( c ) g(c,d)=y^*+a_2(d)-a(c) g ( c , d ) = y ∗ + a 2 ( d ) − a ( c ) , ( c , d ) ∈ C / R × C ⊥ / R (c,d)\in C/R\times C^\perp/R ( c , d ) ∈ C / R × C ⊥ / R .
Proof. A pair ( t , t ′ ) ∈ T 2 (t,t')\in T^2 ( t , t ′ ) ∈ T 2 with odd difference has one element in each half. So ν T ( x ) = N ( x ) + N ( − x ) \nu_T(x)=N(x)+N(-x) ν T ( x ) = N ( x ) + N ( − x ) with N ( x ) = # { ( c , d ) ∈ C / R × C ⊥ / R : g ( c , d ) = x } N(x)=\#\{(c,d)\in C/R\times C^\perp/R:g(c,d)=x\} N ( x ) = # {( c , d ) ∈ C / R × C ⊥ / R : g ( c , d ) = x } .
(i) The $2^{2r}$ characters g ( c , d ) g(c,d) g ( c , d ) are distinct. If g ( c , d ) = g ( c ′ , d ′ ) g(c,d)=g(c',d') g ( c , d ) = g ( c ′ , d ′ ) , then a 2 ( d ) − a 2 ( d ′ ) − a ( c ) + a ( c ′ ) ∈ A ⊥ a_2(d)-a_2(d')-a(c)+a(c')\in A^\perp a 2 ( d ) − a 2 ( d ′ ) − a ( c ) + a ( c ′ ) ∈ A ⊥ , so its ψ \psi ψ -image has zero first coordinate: c + c ′ + d + d ′ ∈ R c+c'+d+d'\in R c + c ′ + d + d ′ ∈ R . Then c + c ′ ∈ C ∩ ( C ⊥ + R ) = C ∩ C ⊥ = R c+c'\in C\cap(C^\perp+R)=C\cap C^\perp=R c + c ′ ∈ C ∩ ( C ⊥ + R ) = C ∩ C ⊥ = R , so c ≡ c ′ c\equiv c' c ≡ c ′ , and then d ≡ d ′ d\equiv d' d ≡ d ′ modulo $R.
(ii) ν ∗ ( g ( c , d ) ) = 2 \nu^*(g(c,d))=2 ν ∗ ( g ( c , d )) = 2 . The vector g ( c , d ) g(c,d) g ( c , d ) is 1 + 2 z 1+2z 1 + 2 z with z = ( u + w ) + d ~ − c ~ + 2 ( ε + u ⋅ d − u ⋅ c ) e 1 z=(u+w)+\tilde d-\tilde c+2(\varepsilon+u\cdot d-u\cdot c)e_1 z = ( u + w ) + d ~ − c ~ + 2 ( ε + u ⋅ d − u ⋅ c ) e 1 , so z ˉ = u + w + c + d \bar z=u+w+c+d z ˉ = u + w + c + d . We compute ∑ z − wt z ˉ ( m o d 4 ) \sum z-\operatorname{wt}\bar z\pmod4 ∑ z − wt z ˉ ( mod 4 ) . First, ∑ z ≡ wt ( u + w ) + wt d − wt c + 2 ε + 2 u ⋅ d − 2 u ⋅ c \sum z\equiv\operatorname{wt}(u+w)+\operatorname{wt}d-\operatorname{wt}c+2\varepsilon+2u\cdot d-2u\cdot c ∑ z ≡ wt ( u + w ) + wt d − wt c + 2 ε + 2 u ⋅ d − 2 u ⋅ c . Second, by (F1) and c ⋅ d = 0 c \cdot d = 0 c ⋅ d = 0 : wt z ˉ = wt ( u + w ) + wt c + wt d + 2 ( u + w ) ⋅ c + 2 ( u + w ) ⋅ d \operatorname{wt}\bar{z} = \operatorname{wt}(u+w) + \operatorname{wt}c + \operatorname{wt}d + 2(u+w)\cdot c + 2(u+w)\cdot d wt z ˉ = wt ( u + w ) + wt c + wt d + 2 ( u + w ) ⋅ c + 2 ( u + w ) ⋅ d . Subtracting, and using − 2 ≡ 2 -2 \equiv2 − 2 ≡ 2 and 4 ≡ 0 4 \equiv0 4 ≡ 0 modulo 4:
Σ z − wt z ˉ ≡ 2 wt c + 2 ε + 2 w ⋅ c + 2 w ⋅ d ≡ 2 ε ( m o d 4 ) , \Sigma z-\operatorname{wt}\bar{z} \equiv2\operatorname{wt}c+2\varepsilon+2w\cdot c+2w\cdot d \equiv2\varepsilon\pmod{4}, Σ z − wt z ˉ ≡ 2 wt c + 2 ε + 2 w ⋅ c + 2 w ⋅ d ≡ 2 ε ( mod 4 ) ,
because w ⋅ c ≡ wt c w\cdot c\equiv\operatorname{wt}c w ⋅ c ≡ wt c and w ⋅ d = 0 w\cdot d=0 w ⋅ d = 0 (w ∈ C w\in C w ∈ C , d ∈ C ⊥ d\in C^\perp d ∈ C ⊥ ). So 2 wt z 1 ≡ 2 ε 2\operatorname{wt}z_1\equiv2\varepsilon 2 wt z 1 ≡ 2 ε , i.e. wt z 1 ≡ ε ≡ n / 2 + 1 \operatorname{wt}z_1\equiv\varepsilon\equiv n/2+1 wt z 1 ≡ ε ≡ n /2 + 1 , and ν ∗ = 2 \nu^*=2 ν ∗ = 2 by Lemma 3.7.
(iii) Counting. By Parseval on H ′ H' H ′ , ∑ χ ∣ S H ^ ( χ ) ∣ 2 = ∣ H ′ ∣ ∣ S ∣ \sum_{\chi}|\widehat{S_H}(\chi)|^2=|H'||S| ∑ χ ∣ S H ( χ ) ∣ 2 = ∣ H ′ ∣∣ S ∣ , so ∑ χ ν ∗ ( χ ) = ∣ T ∣ ∣ H ′ ∣ / ∣ S ∣ = ∣ T ∣ 2 = 2 2 r + 2 \sum_{\chi}\nu^*(\chi)=|T||H'|/|S|=|T|^2=2^{2r+2} ∑ χ ν ∗ ( χ ) = ∣ T ∣∣ H ′ ∣/∣ S ∣ = ∣ T ∣ 2 = 2 2 r + 2 (as ∣ H ′ ∣ = ∣ S ∣ ∣ T ∣ |H'|=|S||T| ∣ H ′ ∣ = ∣ S ∣∣ T ∣ ). By Lemma 3.7 the even part sums to 2 r + 1 + 4 ( 2 r − 1 ) 2 r − 1 = 2 2 r + 1 2^{r+1}+4(2^r-1)2^{r-1}=2^{2r+1} 2 r + 1 + 4 ( 2 r − 1 ) 2 r − 1 = 2 2 r + 1 ; the odd part sums to 2 2 r + 1 2^{2r+1} 2 2 r + 1 , and each odd value is 0 or 2. So exactly 2 2 r 2^{2r} 2 2 r odd characters have ν ∗ = 2 \nu^*=2 ν ∗ = 2 . By (i) and (ii) these are the g ( c , d ) g(c,d) g ( c , d ) .
(iv) ν ∗ ( χ ˉ ) = ν ∗ ( χ ) \nu^*(\bar{\chi})=\nu^*(\chi) ν ∗ ( χ ˉ ) = ν ∗ ( χ ) , because S H ^ ( χ ˉ ) = S H ^ ( χ ) \widehat{S_H}(\bar{\chi})=\widehat{S_H}(\chi) S H ( χ ˉ ) = S H ( χ ) . So the set G = { g ( c , d ) } G=\{g(c,d)\} G = { g ( c , d )} satisfies G = − G G=-G G = − G , and by (i) N ( x ) = [ x ∈ G ] = N ( − x ) N(x)=[x\in G]=N(-x) N ( x ) = [ x ∈ G ] = N ( − x ) . Hence ν T ( x ) = 2 [ x ∈ G ] = ν ∗ ( x ) \nu_T(x)=2[x\in G]=\nu^*(x) ν T ( x ) = 2 [ x ∈ G ] = ν ∗ ( x ) for odd x x x . □
Proof of items 1 and 2
Item 1: L ′ L' L ′ is a lattice of periods and ∣ S ∣ = 2 r + 1 |S|=2^{r+1} ∣ S ∣ = 2 r + 1 (Lemma 3.1); ∣ H ′ ∣ = 2 2 r + 2 |H'|=2^{2r+2} ∣ H ′ ∣ = 2 2 r + 2 (Lemma 3.6(b)); T T T consists of 2 r + 1 2^{r+1} 2 r + 1 distinct characters with the stated multiplicities and disjoint halves (Lemma 3.8).
Item 2: every character of H ′ H' H ′ is χ y \chi_y χ y with y ∈ L ′ ⊥ y\in L'^\perp y ∈ L ′ ⊥ , even or odd. By Lemmas 3.7, 3.9 and 3.10, ∣ T ∣ ∣ S H ^ ( χ ) ∣ 2 = ∣ S ∣ 2 ν ∗ ( χ ) = ∣ S ∣ 2 ν T ( χ ) |T||\widehat{S_H}(\chi)|^2=|S|^2\nu^*(\chi)=|S|^2\nu_T(\chi) ∣ T ∣∣ S H ( χ ) ∣ 2 = ∣ S ∣ 2 ν ∗ ( χ ) = ∣ S ∣ 2 ν T ( χ ) for every χ ∈ H ′ ^ \chi\in\widehat{H'} χ ∈ H ′ : this is the first identity.
Second identity. Let g ∈ H ′ g\in H' g ∈ H ′ . Multiply the first identity by χ ( g ) ‾ \overline{\chi(g)} χ ( g ) and sum over χ ∈ H ′ ^ \chi\in\widehat{H'} χ ∈ H ′ . On the left, ∑ χ ∣ S H ^ ( χ ) ∣ 2 χ ( g ) ‾ = ∣ H ′ ∣ ν S ( g ) \sum_{\chi}|\widehat{S_H}(\chi)|^2\overline{\chi(g)}=|H'|\nu_S(g) ∑ χ ∣ S H ( χ ) ∣ 2 χ ( g ) = ∣ H ′ ∣ ν S ( g ) . On the right, ∑ χ ν T ( χ ) χ ( g ) ‾ = ∑ t , t ′ ∈ T ( t − t ′ ) ( g ) = ∣ ∑ t ∈ T t ( g ) ∣ 2 \sum_{\chi}\nu_T(\chi)\overline{\chi(g)}=\sum_{t,t'\in T}(t-t')(g)=\left|\sum_{t\in T}t(g)\right|^2 ∑ χ ν T ( χ ) χ ( g ) = ∑ t , t ′ ∈ T ( t − t ′ ) ( g ) = ∑ t ∈ T t ( g ) 2 . So ∣ T ∣ ∣ H ′ ∣ ν S ( g ) = ∣ S ∣ 2 ∣ T ^ ( g ) ∣ 2 |T||H'|\nu_S(g)=|S|^2|\widehat{T}(g)|^2 ∣ T ∣∣ H ′ ∣ ν S ( g ) = ∣ S ∣ 2 ∣ T ( g ) ∣ 2 with T ^ ( g ) = ∑ t ∈ T t ( g ) \widehat{T}(g)=\sum_{t\in T}t(g) T ( g ) = ∑ t ∈ T t ( g ) ; with ∣ H ′ ∣ = ∣ S ∣ ∣ T ∣ |H'|=|S||T| ∣ H ′ ∣ = ∣ S ∣∣ T ∣ this is ∣ T ∣ 2 ν S ( g ) = ∣ S ∣ ∣ T ^ ( g ) ∣ 2 |T|^2\nu_S(g)=|S||\widehat{T}(g)|^2 ∣ T ∣ 2 ν S ( g ) = ∣ S ∣∣ T ( g ) ∣ 2 . □
Proof of item 3
We use [CKRS, Cor. 2.7] (equivalently [CKRS, Thm. 2.8]): let P = ⋃ j = 1 N ( Λ + v j ) P=\bigcup_{j=1}^{N}(\Lambda+v_j) P = ⋃ j = 1 N ( Λ + v j ) and Q = ⋃ j = 1 M ( Γ Q + w j ) Q=\bigcup_{j=1}^{M}(\Gamma_Q+w_j) Q = ⋃ j = 1 M ( Γ Q + w j ) with lattices Λ , Γ Q \Lambda,\Gamma_Q Λ , Γ Q , P − P ⊆ Γ Q ∗ P-P\subseteq\Gamma_Q^* P − P ⊆ Γ Q ∗ and Q − Q ⊆ Λ ∗ Q-Q\subseteq\Lambda^* Q − Q ⊆ Λ ∗ . Then P P P and Q Q Q are formally dual iff, for every y ∈ Λ ∗ y\in\Lambda^* y ∈ Λ ∗ ,
∣ N − 1 ∑ j e 2 π i ⟨ v j , y ⟩ ∣ 2 = M − 1 # { ( z , j , k ) : z ∈ Γ Q , y = z + w j − w k } . \left|N^{-1}\sum_j e^{2\pi i\langle v_j,y\rangle}\right|^2=M^{-1}\#\{(z,j,k):z\in\Gamma_Q,\ y=z+w_j-w_k\}. N − 1 j ∑ e 2 π i ⟨ v j , y ⟩ 2 = M − 1 # {( z , j , k ) : z ∈ Γ Q , y = z + w j − w k } .
Take Λ = L ′ \Lambda=L' Λ = L ′ , v j v_j v j the elements of Γ − x 0 \Gamma-x_0 Γ − x 0 representing S S S (N = ∣ S ∣ N=|S| N = ∣ S ∣ ), Γ Q = A ∗ \Gamma_Q=A^* Γ Q = A ∗ , w j = t j / 8 w_j=t_j/8 w j = t j /8 for t j ∈ T t_j\in T t j ∈ T (M = ∣ T ∣ M=|T| M = ∣ T ∣ ). Translation by x 0 x_0 x 0 does not affect formal duality. The t j / 8 t_j/8 t j /8 are distinct modulo A ∗ A^* A ∗ because the t j t_j t j are distinct characters (Lemma 3.8). The hypotheses hold: P − P = Γ − Γ ⊆ A = ( A ∗ ) ∗ P-P=\Gamma-\Gamma\subseteq A=(A^*)^* P − P = Γ − Γ ⊆ A = ( A ∗ ) ∗ ; and Q − Q ⊆ L ′ ∗ Q-Q\subseteq L'^* Q − Q ⊆ L ′ ∗ because A ∗ ⊆ L ′ ∗ A^*\subseteq L'^* A ∗ ⊆ L ′ ∗ (as L ′ ⊆ A L'\subseteq A L ′ ⊆ A ) and T ⊆ L ′ ⊥ T\subseteq L'^\perp T ⊆ L ′ ⊥ gives T / 8 ⊆ L ′ ∗ T/8\subseteq L'^* T /8 ⊆ L ′ ∗ .
Now let y = m / 8 ∈ L ′ ∗ y=m/8\in L'^* y = m /8 ∈ L ′ ∗ , with m m o d 8 ∈ L ′ ⊥ m\bmod8\in L'^\perp m mod 8 ∈ L ′ ⊥ . The left side is ∣ S H ^ ( χ m ) ∣ 2 / ∣ S ∣ 2 |\widehat{S_H}(\chi_m)|^2/|S|^2 ∣ S H ( χ m ) ∣ 2 /∣ S ∣ 2 . On the right, for each pair ( t , t ′ ) ∈ T 2 (t,t')\in T^2 ( t , t ′ ) ∈ T 2 with ( m − t + t ′ ) / 8 ∈ A ∗ (m-t+t')/8\in A^* ( m − t + t ′ ) /8 ∈ A ∗ the element z z z is determined, so the count is # { ( t , t ′ ) : t − t ′ = χ m in L ′ ⊥ / A ⊥ } = ν T ( χ m ) \#\{(t,t'):t-t'=\chi_m\text{ in }L'^\perp/A^\perp\}=\nu_T(\chi_m) # {( t , t ′ ) : t − t ′ = χ m in L ′ ⊥ / A ⊥ } = ν T ( χ m ) (Lemma 3.6(c)); the right side is ν T ( χ m ) / ∣ T ∣ \nu_T(\chi_m)/|T| ν T ( χ m ) /∣ T ∣ . The equality is the first identity of item 2. Hence Γ \Gamma Γ and Q = A ∗ + T / 8 Q=A^*+T/8 Q = A ∗ + T /8 are formally dual. □
Proof of item 4
By Lemmas 3.7, 3.9 and 3.10, ν T \nu_T ν T equals 2 r + 1 2^{r+1} 2 r + 1 at 0, 2 r − 1 2^{r-1} 2 r − 1 on 4 ( 2 r − 1 ) 4(2^r-1) 4 ( 2 r − 1 ) even characters, 2 on the 2 2 r 2^{2r} 2 2 r odd characters g ( c , d ) g(c,d) g ( c , d ) , and 0 elsewhere. These are three disjoint families of characters. For r = 2 r=2 r = 2 the values 2 r − 1 2^{r-1} 2 r − 1 and 2 coincide, and ν T = 2 \nu_T=2 ν T = 2 on 4 ⋅ 3 + 16 = 28 4\cdot3+16=28 4 ⋅ 3 + 16 = 28 characters. The statement on H ′ ^ \widehat{H'} H ′ is Lemma 3.6(e).
Remark (last line of Theorem A). If 1 ∈ R 1 \in R 1 ∈ R then 1 ∈ C ⊥ 1 \in C^{\perp} 1 ∈ C ⊥ , so every c ∈ C c \in C c ∈ C has even weight and c ⋅ c = 0 c \cdot c = 0 c ⋅ c = 0 . The dot product is thus alternating on C C C . Its radical on C C C is C ∩ C ⊥ = R C \cap C^{\perp} = R C ∩ C ⊥ = R , so it is non-degenerate and alternating on C / R C/R C / R , and r = dim C / R r = \dim C/R r = dim C / R is even. This remark was not reviewed.
Proof of item 5
Primitivity in the sense of [KS, Def. 3.1] means two conditions on each of S S S and T T T : not contained in a coset of a proper subgroup, and not a union of cosets of a non-trivial subgroup. For a formally dual pair, S S S lies in a coset of a subgroup K K K iff T T T is a union of cosets of the annihilator K ⊥ K^{\perp} K ⊥ , and symmetrically [KS, Thm. 3.2; CKRS, Lemma 4.2]. So it is enough to show that S S S and T T T lie in no coset of a proper subgroup, that is, that S − S S-S S − S generates H ′ H' H ′ and T − T T-T T − T generates H ^ ′ \widehat{H}' H ′ .
S S S . A = ⟨ Γ − Γ ⟩ A = \langle\Gamma- \Gamma\rangle A = ⟨ Γ − Γ ⟩ , so the differences of S S S generate A / L ′ = H ′ A/L' = H' A / L ′ = H ′ .
T T T . Since h < k h < k h < k , C / R ≠ 0 C/R \ne0 C / R = 0 . Take v ∈ C / R v \in C/R v ∈ C / R , v ≠ 0 v \ne0 v = 0 . As v ∉ R v \notin R v ∈ / R there is c ∈ C c \in C c ∈ C with c ⋅ v = 1 c \cdot v = 1 c ⋅ v = 1 . The differences a ( v ) − a ( 0 ) a(v) - a(0) a ( v ) − a ( 0 ) and a ( c + v ) − a ( c ) a(c+v) - a(c) a ( c + v ) − a ( c ) have ψ \psi ψ -images ( v , F 1 ( v ) ) (v,F_1(v)) ( v , F 1 ( v )) and ( v , F 1 ( v ) + 2 ) (v,F_1(v)+2) ( v , F 1 ( v ) + 2 ) (proof of Lemma 3.9). Their difference is ( 0 , 2 ) (0,2) ( 0 , 2 ) . So ⟨ X 1 − X 1 ⟩ \langle X_1-X_1\rangle ⟨ X 1 − X 1 ⟩ contains ( 0 , 2 ) (0,2) ( 0 , 2 ) and every ( v , s ) (v,s) ( v , s ) with v ∈ C / R v \in C/R v ∈ C / R and s ≡ wt v ( m o d 2 ) s \equiv\operatorname{wt} v \pmod2 s ≡ wt v ( mod 2 ) . The same holds for X 2 X_2 X 2 over C ⊥ / R C^{\perp}/R C ⊥ / R . As R ⊥ = C + C ⊥ R^{\perp} = C+C^{\perp} R ⊥ = C + C ⊥ , and wt ( v 1 + v 2 ) ≡ wt v 1 + wt v 2 ( m o d 2 ) \operatorname{wt}(v_1+v_2) \equiv\operatorname{wt} v_1+\operatorname{wt} v_2 \pmod2 wt ( v 1 + v 2 ) ≡ wt v 1 + wt v 2 ( mod 2 ) , these differences generate the whole of E / A ⊥ \mathcal{E}/A^{\perp} E / A ⊥ , which has index 2 in H ^ ′ \widehat{H}' H ′ (Lemma 3.6(d)). Finally y ∗ − a ( 0 ) = y ∗ ∈ T − T y^*-a(0)=y^* \in T-T y ∗ − a ( 0 ) = y ∗ ∈ T − T is odd. So ⟨ T − T ⟩ = H ^ ′ \langle T-T\rangle=\widehat{H}' ⟨ T − T ⟩ = H ′ . □ \square □
Proof of Proposition I
Items 1 and 2 are identities between sets of residues mod 8 and use no external result. Item 3 uses Theorem A, item 3, and [CKRS, Lemma 2.4]. We use the conventions and facts (F1) to (F4) of § 3.1 and the description of A ∗ A^* A ∗ in (3) . By (3) , 8 Q = 8 A ∗ + T = 2 M + T 8Q = 8A^*+T = 2M+T 8 Q = 8 A ∗ + T = 2 M + T with
M = { z ∈ Z n : z ˉ ∈ R , Σ z ≡ 0 ( m o d 4 ) } . M = \{z \in\mathbb{Z}^n : \bar{z} \in R,\ \Sigma z \equiv0 \pmod4\}. M = { z ∈ Z n : z ˉ ∈ R , Σ z ≡ 0 ( mod 4 )} .
For y ∈ ( Z / 4 ) n y \in(\mathbb{Z}/4)^n y ∈ ( Z /4 ) n , y ˉ \bar{y} y ˉ and Σ y m o d 4 \Sigma y \bmod4 Σ y mod 4 are well defined. For the sign change σ D \sigma_D σ D we have σ D ( y ) ≡ y ( m o d 2 ) \sigma_D(y) \equiv y \pmod2 σ D ( y ) ≡ y ( mod 2 ) , Σ σ D ( y ) ≡ Σ y + 2 D ⋅ y ˉ ( m o d 4 ) \Sigma\sigma_D(y) \equiv\Sigma y + 2D \cdot\bar{y} \pmod4 Σ σ D ( y ) ≡ Σ y + 2 D ⋅ y ˉ ( mod 4 ) (each flipped coordinate changes y i y_i y i to y i − 2 y i y_i-2y_i y i − 2 y i ), and σ D ( 1 ) = 1 − 2 D ~ \sigma_D(1)=1-2\tilde{D} σ D ( 1 ) = 1 − 2 D ~ .
Step 1 (description of 8 Q 8Q 8 Q mod 8). Even points. An element of 2 M + T 2M+T 2 M + T of the first kind is 2 z + 2 c ~ + 4 ( u ⋅ c ) e 1 = 2 y 2z+2\tilde{c}+4(u\cdot c)e_1=2y 2 z + 2 c ~ + 4 ( u ⋅ c ) e 1 = 2 y with z ∈ M z \in M z ∈ M , c ∈ C c \in C c ∈ C , y = z + c ~ + 2 ( u ⋅ c ) e 1 y=z+\tilde{c}+2(u\cdot c)e_1 y = z + c ~ + 2 ( u ⋅ c ) e 1 . Put h ′ = z ˉ ∈ R h'=\bar{z}\in R h ′ = z ˉ ∈ R and b = y ˉ = c + h ′ ∈ C b=\bar{y}=c+h'\in C b = y ˉ = c + h ′ ∈ C . Since Σ z ≡ 0 \Sigma z\equiv0 Σ z ≡ 0 : Σ y ≡ wt c + 2 u ⋅ c \Sigma y\equiv\operatorname{wt}c+2u\cdot c Σ y ≡ wt c + 2 u ⋅ c . By (F1), (F2) and b ⋅ h ′ = 0 b\cdot h'=0 b ⋅ h ′ = 0 : wt c = wt ( b + h ′ ) ≡ wt b + 2 λ ( h ′ ) \operatorname{wt}c=\operatorname{wt}(b+h')\equiv\operatorname{wt}b+2\lambda(h') wt c = wt ( b + h ′ ) ≡ wt b + 2 λ ( h ′ ) ; and 2 u ⋅ c = 2 u ⋅ b + 2 λ ( h ′ ) 2u\cdot c=2u\cdot b+2\lambda(h') 2 u ⋅ c = 2 u ⋅ b + 2 λ ( h ′ ) . Hence
Σ y ≡ wt b + 2 u ⋅ b ( m o d 4 ) , b = y ˉ ∈ C . \Sigma y \equiv\operatorname{wt} b+2u\cdot b \pmod4,\qquad b=\bar{y}\in C. Σ y ≡ wt b + 2 u ⋅ b ( mod 4 ) , b = y ˉ ∈ C .
Odd points. An element of the second kind is 2 z + y ∗ + a 2 ( d ) = 1 + 2 y 2z+y^*+a_2(d)=1+2y 2 z + y ∗ + a 2 ( d ) = 1 + 2 y with y = z + ( u + w ) + d ~ + 2 ( ε + u ⋅ d ) e 1 y=z+(u+w)+\tilde{d}+2(\varepsilon+u\cdot d)e_1 y = z + ( u + w ) + d ~ + 2 ( ε + u ⋅ d ) e 1 . Here b = y ˉ = h ′ + u + w + d b=\bar{y}=h'+u+w+d b = y ˉ = h ′ + u + w + d with h ′ = z ˉ ∈ R h'=\bar{z}\in R h ′ = z ˉ ∈ R , d ∈ C ⊥ d\in C^{\perp} d ∈ C ⊥ , and
Σ y = wt ( u + w ) + wt d + 2 ε + 2 u ⋅ d ( m o d 4 ) . \Sigma y=\operatorname{wt}(u+w)+\operatorname{wt}d+2\varepsilon+2u\cdot d \pmod4. Σ y = wt ( u + w ) + wt d + 2 ε + 2 u ⋅ d ( mod 4 ) .
Step 2 (even points go to E E E ). Let 2 y 2y 2 y be as in Step 1. Then g ( 2 y ) = 2 σ D ( y ) + 2 ( 1 ~ − c ~ 0 ) + 4 v ~ = 2 y ′ g(2y)=2\sigma_D(y)+2(\tilde{1}-\tilde{c}_0)+4\tilde{v}=2y' g ( 2 y ) = 2 σ D ( y ) + 2 ( 1 ~ − c ~ 0 ) + 4 v ~ = 2 y ′ with y ′ = σ D ( y ) + 1 ~ − c ~ 0 + 2 v ~ y'=\sigma_D(y)+\tilde{1}-\tilde{c}_0+2\tilde{v} y ′ = σ D ( y ) + 1 ~ − c ~ 0 + 2 v ~ . Its parity class is y ˉ ′ = b + 1 + c 0 ∈ 1 + C \bar{y}'=b+1+c_0\in1+C y ˉ ′ = b + 1 + c 0 ∈ 1 + C . Its sum is
Σ y ′ ≡ wt b + 2 u ⋅ b + 2 D ⋅ b + n − wt c 0 + 2 wt v ≡ wt b + 2 c 0 ⋅ b + n − wt c 0 + 2 wt v , \Sigma y' \equiv\operatorname{wt}b+2u\cdot b+2D\cdot b+n-\operatorname{wt}c_0+2\operatorname{wt}v \equiv\operatorname{wt}b+2c_0\cdot b+n-\operatorname{wt}c_0+2\operatorname{wt}v, Σ y ′ ≡ wt b + 2 u ⋅ b + 2 D ⋅ b + n − wt c 0 + 2 wt v ≡ wt b + 2 c 0 ⋅ b + n − wt c 0 + 2 wt v ,
because 2 ( u + D ) ⋅ b = 2 ( c 0 + e ) ⋅ b = 2 c 0 ⋅ b 2(u+D)\cdot b=2(c_0+e)\cdot b=2c_0\cdot b 2 ( u + D ) ⋅ b = 2 ( c 0 + e ) ⋅ b = 2 c 0 ⋅ b (e ∈ C ⊥ e\in C^\perp e ∈ C ⊥ , b ∈ C b\in C b ∈ C ). By (F1), − wt y ˉ ′ = − ( n − wt ( b + c 0 ) ) ≡ − n + wt b + wt c 0 + 2 b ⋅ c 0 -\operatorname{wt}\bar y'=-(n-\operatorname{wt}(b+c_0))\equiv-n+\operatorname{wt}b+\operatorname{wt}c_0+2b\cdot c_0 − wt y ˉ ′ = − ( n − wt ( b + c 0 )) ≡ − n + wt b + wt c 0 + 2 b ⋅ c 0 . The difference between this value and Σ y ′ \Sigma y' Σ y ′ is 2 n + 2 ( wt v − wt c 0 ) ≡ 0 2n+2(\operatorname{wt}v-\operatorname{wt}c_0)\equiv0 2 n + 2 ( wt v − wt c 0 ) ≡ 0 (mod 4), since n n n is even and wt v ≡ wt c 0 \operatorname{wt}v\equiv\operatorname{wt}c_0 wt v ≡ wt c 0 (mod 2). By (F4), g ( 2 y ) ∈ E g(2y)\in E g ( 2 y ) ∈ E .
Step 3 (odd points go to O). Let 1 + 2 y 1+2y 1 + 2 y be as in Step 1. Then g ( 1 + 2 y ) = 1 − 2 D ~ + 2 σ D ( y ) + 2 ( 1 ~ − c ~ 0 ) + 4 v ~ = 1 + 2 y ′ g(1+2y)=1-2\widetilde D+2\sigma_D(y)+2(\widetilde1-\widetilde c_0)+4\widetilde v=1+2y' g ( 1 + 2 y ) = 1 − 2 D + 2 σ D ( y ) + 2 ( 1 − c 0 ) + 4 v = 1 + 2 y ′ with y ′ = σ D ( y ) − D ~ + 1 ~ − c ~ 0 + 2 v ~ y'=\sigma_D(y)-\widetilde D+\widetilde1-\widetilde c_0+2\widetilde v y ′ = σ D ( y ) − D + 1 − c 0 + 2 v . Its parity class is y ˉ ′ = 1 + w + d + e + h ′ \bar y'=1+w+d+e+h' y ˉ ′ = 1 + w + d + e + h ′ , which lies in C ⊥ C^\perp C ⊥ : 1 + w ∈ C ⊥ 1+w\in C^\perp 1 + w ∈ C ⊥ by (F3), and d , e , h ′ ∈ C ⊥ d,e,h'\in C^\perp d , e , h ′ ∈ C ⊥ . Next we compute Σ y ′ ≡ Σ y + 2 D ⋅ b − wt D + n − wt c 0 + 2 wt v \Sigma y'\equiv\Sigma y+2D\cdot b-\operatorname{wt}D+n-\operatorname{wt}c_0+2\operatorname{wt}v Σ y ′ ≡ Σ y + 2 D ⋅ b − wt D + n − wt c 0 + 2 wt v modulo 4. We use D = u + c 0 + e D=u+c_0+e D = u + c 0 + e , b = h ′ + u + w + d b=h'+u+w+d b = h ′ + u + w + d and these facts: u ⋅ h ′ = λ ( h ′ ) u\cdot h'=\lambda(h') u ⋅ h ′ = λ ( h ′ ) ; c 0 ⋅ h ′ = c 0 ⋅ d = e ⋅ h ′ = e ⋅ w = 0 c_0\cdot h'=c_0\cdot d=e\cdot h'=e\cdot w=0 c 0 ⋅ h ′ = c 0 ⋅ d = e ⋅ h ′ = e ⋅ w = 0 ; c 0 ⋅ w = wt c 0 c_0\cdot w=\operatorname{wt}c_0 c 0 ⋅ w = wt c 0 . They give, modulo 2,
D ⋅ b ≡ λ ( h ′ ) + wt u + u ⋅ w + u ⋅ d + c 0 ⋅ u + wt c 0 + e ⋅ u + e ⋅ d . D\cdot b\equiv\lambda(h')+\operatorname{wt}u+u\cdot w+u\cdot d+c_0\cdot u+\operatorname{wt}c_0+e\cdot u+e\cdot d. D ⋅ b ≡ λ ( h ′ ) + wt u + u ⋅ w + u ⋅ d + c 0 ⋅ u + wt c 0 + e ⋅ u + e ⋅ d .
By (F1), wt D ≡ wt u + wt c 0 + wt e + 2 u ⋅ c 0 + 2 u ⋅ e \operatorname{wt}D\equiv\operatorname{wt}u+\operatorname{wt}c_0+\operatorname{wt}e+2u\cdot c_0+2u\cdot e wt D ≡ wt u + wt c 0 + wt e + 2 u ⋅ c 0 + 2 u ⋅ e and wt ( u + w ) ≡ wt u + wt w + 2 u ⋅ w \operatorname{wt}(u+w)\equiv\operatorname{wt}u+\operatorname{wt}w+2u\cdot w wt ( u + w ) ≡ wt u + wt w + 2 u ⋅ w . Substituting, all cross terms cancel in pairs and
Σ y ′ ≡ wt w + wt d + 2 ε + 2 λ ( h ′ ) + 2 wt u + 2 e ⋅ d + n − wt e + 2 wt v . \Sigma y'\equiv\operatorname{wt}w+\operatorname{wt}d+2\varepsilon+2\lambda(h')+2\operatorname{wt}u+2e\cdot d+n-\operatorname{wt}e+2\operatorname{wt}v. Σ y ′ ≡ wt w + wt d + 2 ε + 2 λ ( h ′ ) + 2 wt u + 2 e ⋅ d + n − wt e + 2 wt v .
On the other hand wt y ˉ ′ = n − wt ( w + d + e + h ′ ) \operatorname{wt}\bar y'=n-\operatorname{wt}(w+d+e+h') wt y ˉ ′ = n − wt ( w + d + e + h ′ ) , and by (F1) (using w ⋅ d = w ⋅ e = w ⋅ h ′ = d ⋅ h ′ = e ⋅ h ′ = 0 w\cdot d=w\cdot e=w\cdot h'=d\cdot h'=e\cdot h'=0 w ⋅ d = w ⋅ e = w ⋅ h ′ = d ⋅ h ′ = e ⋅ h ′ = 0 and wt h ′ ≡ 2 λ ( h ′ ) \operatorname{wt}h'\equiv2\lambda(h') wt h ′ ≡ 2 λ ( h ′ ) ), wt ( w + d + e + h ′ ) ≡ wt w + wt d + wt e + 2 λ ( h ′ ) + 2 d ⋅ e \operatorname{wt}(w+d+e+h')\equiv\operatorname{wt}w+\operatorname{wt}d+\operatorname{wt}e+2\lambda(h')+2d\cdot e wt ( w + d + e + h ′ ) ≡ wt w + wt d + wt e + 2 λ ( h ′ ) + 2 d ⋅ e . So the value required by (F4) is
2 − wt y ˉ ′ ≡ 2 − n + wt w + wt d + wt e + 2 λ ( h ′ ) + 2 d ⋅ e . 2-\operatorname{wt}\bar y'\equiv2-n+\operatorname{wt}w+\operatorname{wt}d+\operatorname{wt}e+2\lambda(h')+2d\cdot e. 2 − wt y ˉ ′ ≡ 2 − n + wt w + wt d + wt e + 2 λ ( h ′ ) + 2 d ⋅ e .
The difference between the required value and Σ y ′ \Sigma y' Σ y ′ is 2 ( ε + 1 + wt u + wt e + wt v ) ≡ 2 ( ε + 1 + wt D ) 2(\varepsilon+1+\operatorname{wt}u+\operatorname{wt}e+\operatorname{wt}v)\equiv2(\varepsilon+1+\operatorname{wt}D) 2 ( ε + 1 + wt u + wt e + wt v ) ≡ 2 ( ε + 1 + wt D ) (mod 4), using wt v ≡ wt c 0 \operatorname{wt}v\equiv\operatorname{wt}c_0 wt v ≡ wt c 0 . It vanishes iff wt D ≡ ε + 1 ≡ n / 2 \operatorname{wt}D\equiv\varepsilon+1\equiv n/2 wt D ≡ ε + 1 ≡ n /2 (mod 2), which is the hypothesis on f f f . By (F4), g ( 1 + 2 y ) ∈ O g(1+2y)\in O g ( 1 + 2 y ) ∈ O .
Step 4 (counting; end of item 1). The set 8 Q = 2 M + T 8Q=2M+T 8 Q = 2 M + T is invariant under 8 Z n 8\mathbb Z^n 8 Z n , since 4 e i ∈ M 4e_i\in M 4 e i ∈ M . The map g g g satisfies g ( x + 8 z ) = g ( x ) + 8 σ D z g(x+8z)=g(x)+8\sigma_Dz g ( x + 8 z ) = g ( x ) + 8 σ D z , so it induces a bijection of ( Z / 8 ) n (\mathbb Z/8)^n ( Z /8 ) n . By Steps 2 and 3, g g g maps the residues of 8 Q 8Q 8 Q into Γ 8 \Gamma_8 Γ 8 . We bound ∣ 8 Q m o d 8 ∣ |8Q\mathbin{\bmod}8| ∣8 Q mod 8∣ from below. Even part: for b ∈ C b\in C b ∈ C take z = 0 z=0 z = 0 , c = b c=b c = b , y 0 = b ~ + 2 ( u ⋅ b ) e 1 y_0=\widetilde b+2(u\cdot b)e_1 y 0 = b + 2 ( u ⋅ b ) e 1 . For every word s s s of even weight, z = 2 s ~ ∈ M z=2\widetilde s\in M z = 2 s ∈ M (z ˉ = 0 \bar z=0 z ˉ = 0 , Σ z = 2 wt s ≡ 0 \Sigma z=2\operatorname{wt}s\equiv0 Σ z = 2 wt s ≡ 0 ), so y 0 + 2 s ~ y_0+2\widetilde s y 0 + 2 s also occurs. These are 2 n − 1 2^{n-1} 2 n − 1 distinct residues mod 4 with y ˉ = b \bar y=b y ˉ = b . Odd part: for b ∈ u + w + C ⊥ b\in u+w+C^\perp b ∈ u + w + C ⊥ take h ′ = 0 h'=0 h ′ = 0 and d = b + u + w d=b+u+w d = b + u + w , and add 2 s ~ 2\widetilde s 2 s in the same way: 2 n − 1 2^{n-1} 2 n − 1 distinct residues with y ˉ = b \bar y=b y ˉ = b . Distinct b b b give distinct y ˉ \bar y y ˉ . So ∣ 8 Q m o d 8 ∣ ≥ 2 ⋅ 2 n − 1 = 2 n + k = ∣ Γ 8 ∣ |8Q\mathbin{\bmod}8|\ge2\cdot2^{n-1}=2^{n+k}=|\Gamma_8| ∣8 Q mod 8∣ ≥ 2 ⋅ 2 n − 1 = 2 n + k = ∣ Γ 8 ∣ . As g g g is injective on residues and g ( 8 Q m o d 8 ) ⊆ Γ 8 g(8Q\mathbin{\bmod}8)\subseteq\Gamma_8 g ( 8 Q mod 8 ) ⊆ Γ 8 , we get g ( 8 Q m o d 8 ) = Γ 8 g(8Q\mathbin{\bmod}8)=\Gamma_8 g ( 8 Q mod 8 ) = Γ 8 , hence g ( 8 Q ) = Γ g(8Q)=\Gamma g ( 8 Q ) = Γ . The computation used only c 0 ∈ C c_0\in C c 0 ∈ C , e ∈ C ⊥ e\in C^\perp e ∈ C ⊥ , c 0 + e = f c_0+e=f c 0 + e = f and wt v ≡ wt c 0 \operatorname{wt}v\equiv\operatorname{wt}c_0 wt v ≡ wt c 0 , so any decomposition of f f f works. This proves item 1.
Step 5 (item 2). Since wt x ≡ x ⋅ 1 \operatorname{wt}x\equiv x\cdot1 wt x ≡ x ⋅ 1 (mod 2), the condition is ( u + f ) ⋅ 1 ≡ n / 2 (u+f)\cdot1\equiv n/2 ( u + f ) ⋅ 1 ≡ n /2 . If 1 ∈ R 1\in R 1 ∈ R : u ⋅ 1 = λ ( 1 ) = n / 2 u\cdot1=\lambda(1)=n/2 u ⋅ 1 = λ ( 1 ) = n /2 (mod 2) and f ⋅ 1 = 0 f\cdot1=0 f ⋅ 1 = 0 for every f ∈ R ⊥ f\in R^\perp f ∈ R ⊥ , so every f f f works. For f = 0 f=0 f = 0 (so c 0 = e = 0 c_0=e=0 c 0 = e = 0 , v = 0 v=0 v = 0 ) we get D = u D=u D = u , τ = 2 ⋅ 1 \tau=2\cdot1 τ = 2 ⋅ 1 and g ( x ) = σ u x + 2 ⋅ 1 g(x)=\sigma_u x+2\cdot1 g ( x ) = σ u x + 2 ⋅ 1 . If 1 ∉ R 1\notin R 1 ∈ / R : the form f ↦ f ⋅ 1 f\mapsto f\cdot1 f ↦ f ⋅ 1 is non-zero on R ⊥ R^\perp R ⊥ (otherwise 1 ∈ ( R ⊥ ) ⊥ = R 1\in(R^\perp)^\perp=R 1 ∈ ( R ⊥ ) ⊥ = R ), so R ⊥ R^\perp R ⊥ contains an odd word f 1 f_1 f 1 ; if f = 0 f=0 f = 0 and f = f 1 f=f_1 f = f 1 exactly one satisfies the condition.
Step 6 (item 3). By (F4), Γ \Gamma Γ is a union of 2 3 k 2^{3k} 2 3 k translates of 8 Z n 8\mathbb Z^n 8 Z n , so its density is δ ( Γ ) = 2 3 k / 8 n = 2 − 3 k \delta(\Gamma)=2^{3k}/8^n=2^{-3k} δ ( Γ ) = 2 3 k / 8 n = 2 − 3 k . Scaling by 1 / ( 2 2 ) 1/(2\sqrt2) 1/ ( 2 2 ) multiplies the density by ( 2 2 ) n = 2 3 k (2\sqrt2)^n=2^{3k} ( 2 2 ) n = 2 3 k , so δ ( P ) = 1 \delta(P)=1 δ ( P ) = 1 for P = Γ / ( 2 2 ) P=\Gamma/(2\sqrt2) P = Γ/ ( 2 2 ) . Since σ D − 1 = σ D \sigma_D^{-1}=\sigma_D σ D − 1 = σ D , item 1 gives 8 Q = g − 1 ( Γ ) = σ D ( Γ − τ ) 8Q=g^{-1}(\Gamma)=\sigma_D(\Gamma-\tau) 8 Q = g − 1 ( Γ ) = σ D ( Γ − τ ) , i.e. Q = σ D ( Γ − τ ) / 8 Q=\sigma_D(\Gamma-\tau)/8 Q = σ D ( Γ − τ ) /8 , which is the image of Γ / 8 \Gamma/8 Γ/8 under an isometry of R n \mathbb R^n R n . By Theorem A, item 3, Γ \Gamma Γ and Q Q Q are formally dual. [CKRS], Lemma 2.4 says that if P 1 , Q 1 P_1,Q_1 P 1 , Q 1 are formally dual and φ ∈ G L n ( R ) \varphi\in GL_n(\mathbb R) φ ∈ G L n ( R ) , then φ ( P 1 ) \varphi(P_1) φ ( P 1 ) and ( φ T ) − 1 ( Q 1 ) (\varphi^T)^{-1}(Q_1) ( φ T ) − 1 ( Q 1 ) are formally dual. With φ = I / ( 2 2 ) \varphi=I/(2\sqrt2) φ = I / ( 2 2 ) : φ ( Γ ) = P \varphi(\Gamma)=P φ ( Γ ) = P and ( φ T ) − 1 ( Q ) = 2 2 Q = σ D ( Γ − τ ) / ( 2 2 ) = σ D ( P − τ / ( 2 2 ) ) (\varphi^T)^{-1}(Q)=2\sqrt2Q=\sigma_D(\Gamma-\tau)/(2\sqrt2)=\sigma_D(P-\tau/(2\sqrt2)) ( φ T ) − 1 ( Q ) = 2 2 Q = σ D ( Γ − τ ) / ( 2 2 ) = σ D ( P − τ / ( 2 2 )) . This is an isometric copy of P P P , so P P P is formally isodual in the sense of [CKS], which does not require the isometry to be proper. The determinant of σ D \sigma_D σ D is ( − 1 ) wt D (-1)^{\operatorname{wt}D} ( − 1 ) wt D ; the isometry is improper when n / 2 n/2 n /2 is odd (for instance n = 18 n=18 n = 18 and 30 30 30 ), which the definition in [CKS] allows. □
Proof of the remark on formal self-duality
Let C C C be a binary [ 2 k , k ] [2k,k] [ 2 k , k ] code, R = C ∩ C ⊥ R=C\cap C^{\perp} R = C ∩ C ⊥ , Γ = Γ ( C , C ⊥ ) \Gamma=\Gamma(C,C^{\perp}) Γ = Γ ( C , C ⊥ ) , P = Γ / ( 2 2 ) P=\Gamma/(2\sqrt{2}) P = Γ/ ( 2 2 ) , n = 2 k n=2k n = 2 k . We prove: P P P is formally self-dual if and only if k k k is even and R R R is doubly even. Both directions are proved directly, without Theorem A, and the proof does not use C ≠ C ⊥ C\ne C^{\perp} C = C ⊥ . We use (F1) to (F4) of § 3.0, the description of E E E and O O O by X E X_E X E and X O X_O X O below, and the transform of § 3.2 and § 3.5.
The criterion
The pair sums Σ f \Sigma_f Σ f of P P P are unchanged by a translation of P P P and by P ↦ − P P\mapsto-P P ↦ − P . So formally self-dual (formally dual to P P P itself) is equivalent to formally dual to a translate of P P P or of − P -P − P [CKS]. By [CKRS, Cor. 2.7] with Q = P Q=P Q = P and Λ = 2 2 Z n \Lambda=2\sqrt{2}\mathbb{Z}^n Λ = 2 2 Z n (a lattice of periods of P P P ; P − P ⊆ Λ ∗ = Z n / ( 2 2 ) P-P\subseteq\Lambda^*=\mathbb{Z}^n/(2\sqrt{2}) P − P ⊆ Λ ∗ = Z n / ( 2 2 ) since Γ − Γ ⊆ Z n \Gamma-\Gamma\subseteq\mathbb{Z}^n Γ − Γ ⊆ Z n ), P P P is formally self-dual iff for every ℓ ∈ Z n \ell\in\mathbb{Z}^n ℓ ∈ Z n , with y = ℓ / ( 2 2 ) y=\ell/(2\sqrt{2}) y = ℓ / ( 2 2 ) ,
∣ N − 1 ∑ γ ∈ Γ 8 ζ ⟨ γ , ℓ ⟩ ∣ 2 = N − 1 # { ( γ , γ ′ ) ∈ Γ 8 2 : γ − γ ′ ≡ ℓ ( m o d 8 ) } , N = ∣ Γ 8 ∣ = 2 3 k . \left|N^{-1}\sum_{\gamma\in\Gamma_8}\zeta^{\langle\gamma,\ell\rangle}\right|^2=N^{-1}\#\{(\gamma,\gamma')\in\Gamma_8^2:\gamma-\gamma'\equiv\ell\pmod8\},\qquad N=|\Gamma_8|=2^{3k}. N − 1 γ ∈ Γ 8 ∑ ζ ⟨ γ , ℓ ⟩ 2 = N − 1 # {( γ , γ ′ ) ∈ Γ 8 2 : γ − γ ′ ≡ ℓ ( mod 8 )} , N = ∣ Γ 8 ∣ = 2 3 k .
Write F ( z ) = S ^ 8 ( z ) = ∑ γ ∈ Γ 8 ζ ⟨ γ , z ⟩ F(z)=\widehat{S}_8(z)=\sum_{\gamma\in\Gamma_8}\zeta^{\langle\gamma,z\rangle} F ( z ) = S 8 ( z ) = ∑ γ ∈ Γ 8 ζ ⟨ γ , z ⟩ and ν 8 ( z ) = # { ( γ , γ ′ ) ∈ Γ 8 2 : γ − γ ′ ≡ z ( m o d 8 ) } \nu_8(z)=\#\{(\gamma,\gamma')\in\Gamma_8^2:\gamma-\gamma'\equiv z\pmod8\} ν 8 ( z ) = # {( γ , γ ′ ) ∈ Γ 8 2 : γ − γ ′ ≡ z ( mod 8 )} for z ∈ ( Z / 8 ) n z\in(\mathbb{Z}/8)^n z ∈ ( Z /8 ) n . The criterion is
∣ F ( z ) ∣ 2 = 2 3 k ν 8 ( z ) for every z ∈ ( Z / 8 ) n . (9) |F(z)|^2=2^{3k}\nu_8(z)\qquad\text{for every }z\in(\mathbb{Z}/8)^n. \tag*{(9)} ∣ F ( z ) ∣ 2 = 2 3 k ν 8 ( z ) for every z ∈ ( Z /8 ) n . (9)
By (F4), Γ 8 = 2 X E ∪ ( 1 + 2 X O ) \Gamma_8=2X_E\cup(1+2X_O) Γ 8 = 2 X E ∪ ( 1 + 2 X O ) with X E = { x ∈ ( Z / 4 ) n : x ˉ ∈ 1 + C , Σ x ≡ − wt x ˉ } X_E=\{x\in(\mathbb{Z}/4)^n:\bar{x}\in1+C,\ \Sigma x\equiv-\operatorname{wt}\bar{x}\} X E = { x ∈ ( Z /4 ) n : x ˉ ∈ 1 + C , Σ x ≡ − wt x ˉ } and X O = { x : x ˉ ∈ C ⊥ , Σ x ≡ 2 − wt x ˉ } X_O=\{x:\bar{x}\in C^{\perp},\ \Sigma x\equiv2-\operatorname{wt}\bar{x}\} X O = { x : x ˉ ∈ C ⊥ , Σ x ≡ 2 − wt x ˉ } ; each class x ˉ \bar{x} x ˉ has 2 n − 1 2^{n-1} 2 n − 1 lifts in X E X_E X E (resp. X O X_O X O ).
Residues z z z with z ˉ ∉ { 0 , 1 } \bar{z}\notin\{0,1\} z ˉ ∈ / { 0 , 1 }
Here F ( z ) = 0 F(z)=0 F ( z ) = 0 (Lemma 3.2). Also ν 8 ( z ) = 0 \nu_8(z)=0 ν 8 ( z ) = 0 : a difference of two points of the same half is even, and a difference of points of different halves has all coordinates odd. So (T) holds.
Even residues z = 2 y z=2y z = 2 y , y ∈ ( Z / 4 ) n y\in(\mathbb{Z}/4)^n y ∈ ( Z /4 ) n
Transform. By (xref)(3.2.1), F ( 2 y ) = 2 n − 1 + k ( ( − 1 ) wt y ˉ [ y ˉ ∈ C ⊥ ] + i Σ y [ y ˉ ∈ C ] ) F(2y)=2^{n-1+k}\left((-1)^{\operatorname{wt}\bar{y}}[\bar{y}\in C^{\perp}]+i^{\Sigma y}[\bar{y}\in C]\right) F ( 2 y ) = 2 n − 1 + k ( ( − 1 ) wt y ˉ [ y ˉ ∈ C ⊥ ] + i Σ y [ y ˉ ∈ C ] ) , hence ∣ F ( 2 y ) ∣ 2 / 2 3 k |F(2y)|^2/2^{3k} ∣ F ( 2 y ) ∣ 2 / 2 3 k equals
[ Σ y ≡ 0 ( m o d 4 ) ] [\Sigma y\equiv0\pmod4] [ Σ y ≡ 0 ( mod 4 )] if y ˉ ∈ R \bar{y}\in R y ˉ ∈ R (the words of R R R are even, so the bracket is ∣ 1 + i Σ y ∣ 2 |1+i^{\Sigma y}|^2 ∣1 + i Σ y ∣ 2 , and Σ y \Sigma y Σ y is even);
2 3 k − 2 2^{3k-2} 2 3 k − 2 if y ˉ ∈ ( C ∪ C ⊥ ) ∖ R \bar{y}\in(C\cup C^{\perp})\setminus R y ˉ ∈ ( C ∪ C ⊥ ) ∖ R (one term only);
0 0 0 otherwise.
Pair count. A difference ≡ 2 y \equiv2y ≡ 2 y comes from two points of the same half. For two points 2 x , 2 x ′ 2x,2x' 2 x , 2 x ′ of 2 X E 2X_E 2 X E with x = x ′ + y x=x'+y x = x ′ + y we need x ˉ ′ ∈ 1 + C \bar{x}'\in1+C x ˉ ′ ∈ 1 + C and x ˉ ′ + y ˉ ∈ 1 + C \bar{x}'+\bar{y}\in1+C x ˉ ′ + y ˉ ∈ 1 + C , so y ˉ ∈ C \bar{y}\in C y ˉ ∈ C ; and the sum condition Σ x ≡ − wt x ˉ \Sigma x\equiv-\operatorname{wt}\bar{x} Σ x ≡ − wt x ˉ , given Σ x ′ ≡ − wt x ˉ ′ \Sigma x'\equiv-\operatorname{wt}\bar{x}' Σ x ′ ≡ − wt x ˉ ′ , reads (by (F1)) Σ y + wt y ˉ ≡ 2 x ˉ ′ ⋅ y ˉ ( m o d 4 ) \Sigma y+\operatorname{wt}\bar{y}\equiv2\bar{x}'\cdot\bar{y}\pmod4 Σ y + wt y ˉ ≡ 2 x ˉ ′ ⋅ y ˉ ( mod 4 ) . Write x ˉ ′ = 1 + p \bar{x}'=1+p x ˉ ′ = 1 + p , p ∈ C p\in C p ∈ C , so x ˉ ′ ⋅ y ˉ = wt y ˉ + p ⋅ y ˉ \bar{x}'\cdot\bar{y}=\operatorname{wt}\bar{y}+p\cdot\bar{y} x ˉ ′ ⋅ y ˉ = wt y ˉ + p ⋅ y ˉ .
If y ˉ ∈ R \bar{y}\in R y ˉ ∈ R : p ⋅ y ˉ = 0 p\cdot\bar{y}=0 p ⋅ y ˉ = 0 and wt y ˉ \operatorname{wt}\bar{y} wt y ˉ is even, so the condition is Σ y ≡ wt y ˉ ( m o d 4 ) \Sigma y\equiv\operatorname{wt}\bar{y}\pmod4 Σ y ≡ wt y ˉ ( mod 4 ) , independent of p p p . Each of the 2 k 2^k 2 k classes x ˉ ′ \bar{x}' x ˉ ′ has 2 n − 1 2^{n-1} 2 n − 1 lifts: 2 3 k − 1 2^{3k-1} 2 3 k − 1 pairs in 2 X E 2X_E 2 X E when the condition holds.
If y ˉ ∈ C ∖ R \bar{y}\in C\setminus R y ˉ ∈ C ∖ R : p ↦ p ⋅ y ˉ p\mapsto p\cdot\bar{y} p ↦ p ⋅ y ˉ is a non-zero form on C C C (y ˉ ∉ C ⊥ \bar{y}\notin C^{\perp} y ˉ ∈ / C ⊥ ), and for each p p p the condition fixes the value of p ⋅ y ˉ p\cdot\bar{y} p ⋅ y ˉ (the left side is even): 2 k − 1 2^{k-1} 2 k − 1 classes, 2 3 k − 2 2^{3k-2} 2 3 k − 2 pairs.
For two points of 1 + 2 X O 1+2X_O 1 + 2 X O the same computation, with x ˉ ′ = a ∈ C ⊥ \bar{x}'=a\in C^\perp x ˉ ′ = a ∈ C ⊥ , requires y ˉ ∈ C ⊥ \bar{y}\in C^\perp y ˉ ∈ C ⊥ and gives the same congruence; a ⋅ y ˉ = 0 a\cdot\bar{y}=0 a ⋅ y ˉ = 0 if y ˉ ∈ R \bar{y}\in R y ˉ ∈ R , and the form a ↦ a ⋅ y ˉ a\mapsto a\cdot\bar{y} a ↦ a ⋅ y ˉ is non-zero on C ⊥ C^\perp C ⊥ if y ˉ ∈ C ⊥ ∖ R \bar{y}\in C^\perp\setminus R y ˉ ∈ C ⊥ ∖ R . Adding the two halves:
ν 8 ( 2 y ) = { 2 3 k [ Σ y ≡ wt y ˉ ( 4 ) ] y ˉ ∈ R , 2 3 k − 2 y ˉ ∈ ( C ∪ C ⊥ ) ∖ R , 0 otherwise . \nu_8(2y)=\begin{cases}
2^{3k}[\Sigma y\equiv\operatorname{wt}\bar{y}\ (4)] & \bar{y}\in R,\\
2^{3k-2} & \bar{y}\in(C\cup C^\perp)\setminus R,\\
0 & \text{otherwise}.
\end{cases} ν 8 ( 2 y ) = ⎩ ⎨ ⎧ 2 3 k [ Σ y ≡ wt y ˉ ( 4 )] 2 3 k − 2 0 y ˉ ∈ R , y ˉ ∈ ( C ∪ C ⊥ ) ∖ R , otherwise .
Comparison. (T) holds at every 2 y 2y 2 y with y ˉ ∉ R \bar{y}\notin R y ˉ ∈ / R . For y ˉ ∈ R \bar{y}\in R y ˉ ∈ R it requires [ Σ y ≡ 0 ] = [ Σ y ≡ wt y ˉ ] [\Sigma y\equiv0]=[\Sigma y\equiv\operatorname{wt}\bar{y}] [ Σ y ≡ 0 ] = [ Σ y ≡ wt y ˉ ] for Σ y ∈ { 0 , 2 } \Sigma y\in\{0,2\} Σ y ∈ { 0 , 2 } , i.e. wt y ˉ ≡ 0 ( m o d 4 ) \operatorname{wt}\bar{y}\equiv0\pmod4 wt y ˉ ≡ 0 ( mod 4 ) ; both lifts occur for every y ˉ ∈ R \bar{y}\in R y ˉ ∈ R . So:
(T) holds at all even z ⟺ R is doubly even (for every k ) . (10) \text{(T) holds at all even }z\Longleftrightarrow R\text{ is doubly even}\qquad\text{(for every }k\text{)}. \tag*{(10)} (T) holds at all even z ⟺ R is doubly even (for every k ) . (10)
Odd residues z = 1 + 2 y z=1+2y z = 1 + 2 y , and conclusion
Put t = ( Σ y − wt y ˉ ) / 2 ( m o d 2 ) t=(\Sigma y-\operatorname{wt}\bar{y})/2\pmod2 t = ( Σ y − wt y ˉ ) /2 ( mod 2 ) , which equals wt y 1 \operatorname{wt}y_1 wt y 1 in the notation of § 3.1 .
Transform. Formula (3.5.1) holds for every y y y . It gives ∣ F ( 1 + 2 y ) ∣ 2 = 2 2 n ∣ G C ⊥ ( y ˉ ) ∣ 2 [ t ≢ k ( m o d 2 ) ] |F(1+2y)|^2=2^{2n}|G_{C^\perp}(\bar{y})|^2[t\not\equiv k\pmod2] ∣ F ( 1 + 2 y ) ∣ 2 = 2 2 n ∣ G C ⊥ ( y ˉ ) ∣ 2 [ t ≡ k ( mod 2 )] . By the first form of Lemma 3.3 (with K = C ⊥ K=C^\perp K = C ⊥ ), ∣ G C ⊥ ( w ) ∣ 2 = 2 k ∑ d ∈ R i − wt d ( − 1 ) d ⋅ w |G_{C^\perp}(w)|^2=2^k\sum_{d\in R}i^{-\operatorname{wt}d}(-1)^{d\cdot w} ∣ G C ⊥ ( w ) ∣ 2 = 2 k ∑ d ∈ R i − wt d ( − 1 ) d ⋅ w . If R R R is doubly even this is 2 k + h [ w ∈ R ⊥ ] 2^{k+h}[w\in R^\perp] 2 k + h [ w ∈ R ⊥ ] , so
∣ F ( 1 + 2 y ) ∣ 2 = 2 5 k + h [ y ˉ ∈ R ⊥ ] [ t ≢ k ] ( R doubly even ) . |F(1+2y)|^2=2^{5k+h}[\bar{y}\in R^\perp][t\not\equiv k]\qquad(R\text{ doubly even}). ∣ F ( 1 + 2 y ) ∣ 2 = 2 5 k + h [ y ˉ ∈ R ⊥ ] [ t ≡ k ] ( R doubly even ) .
Pair count (any R R R ). Only pairs with one point in each half contribute.
Pairs ( 1 + 2 x , 2 x ′ ) (1+2x,2x') ( 1 + 2 x , 2 x ′ ) , x ∈ X O x\in X_O x ∈ X O , x ′ ∈ X E x'\in X_E x ′ ∈ X E : the difference is ≡ 1 + 2 y \equiv1+2y ≡ 1 + 2 y iff x = x ′ + y x=x'+y x = x ′ + y in ( Z / 4 ) n (\mathbb{Z}/4)^n ( Z /4 ) n . Put b = x ˉ ′ ∈ ( 1 + C ) ∩ ( y ˉ + C ⊥ ) b=\bar{x}'\in(1+C)\cap(\bar{y}+C^\perp) b = x ˉ ′ ∈ ( 1 + C ) ∩ ( y ˉ + C ⊥ ) . This set is non-empty iff y ˉ ∈ 1 + C + C ⊥ = R ⊥ \bar{y}\in1+C+C^\perp=R^\perp y ˉ ∈ 1 + C + C ⊥ = R ⊥ , and then it is a coset b 0 + R b_0+R b 0 + R (2 h 2^h 2 h words). By (F1) the sum conditions reduce to t + wt y ˉ ≡ 1 + b ⋅ y ˉ ( m o d 2 ) t+\operatorname{wt}\bar{y}\equiv1+b\cdot\bar{y}\pmod2 t + wt y ˉ ≡ 1 + b ⋅ y ˉ ( mod 2 ) . On the coset b ⋅ y ˉ = b 0 ⋅ y ˉ b\cdot\bar{y}=b_0\cdot\bar{y} b ⋅ y ˉ = b 0 ⋅ y ˉ (as y ˉ ∈ R ⊥ \bar{y}\in R^\perp y ˉ ∈ R ⊥ ). Write b 0 = 1 + p = y ˉ + a b_0=1+p=\bar{y}+a b 0 = 1 + p = y ˉ + a with p ∈ C p\in C p ∈ C , a ∈ C ⊥ a\in C^\perp a ∈ C ⊥ ; then b 0 ⋅ y ˉ = wt b 0 + ( 1 + p ) ⋅ a = wt b 0 + wt a ≡ wt y ˉ b_0\cdot\bar{y}=\operatorname{wt}b_0+(1+p)\cdot a=\operatorname{wt}b_0+\operatorname{wt}a\equiv\operatorname{wt}\bar{y} b 0 ⋅ y ˉ = wt b 0 + ( 1 + p ) ⋅ a = wt b 0 + wt a ≡ wt y ˉ . So the condition is t ≡ 1 t\equiv1 t ≡ 1 , and the count is 2 n − 1 + h [ y ˉ ∈ R ⊥ ] [ t ≡ 1 ] 2^{n-1+h}[\bar{y}\in R^\perp][t\equiv1] 2 n − 1 + h [ y ˉ ∈ R ⊥ ] [ t ≡ 1 ] .
Pairs ( 2 x , 1 + 2 x ′ ) (2x,1+2x') ( 2 x , 1 + 2 x ′ ) , x ∈ X E x\in X_E x ∈ X E , x ′ ∈ X O x'\in X_O x ′ ∈ X O : the difference is ≡ 1 + 2 y \equiv1+2y ≡ 1 + 2 y iff x = x ′ + y + 1 ~ x=x'+y+\widetilde{1} x = x ′ + y + 1 . Put a = x ˉ ′ ∈ ( y ˉ + C ) ∩ C ⊥ a=\bar{x}'\in(\bar{y}+C)\cap C^\perp a = x ˉ ′ ∈ ( y ˉ + C ) ∩ C ⊥ , non-empty iff y ˉ ∈ R ⊥ \bar{y}\in R^\perp y ˉ ∈ R ⊥ , a coset of R R R . The sum conditions reduce to 1 + t ≡ wt a + a ⋅ y ˉ 1+t\equiv\operatorname{wt}a+a\cdot\bar{y} 1 + t ≡ wt a + a ⋅ y ˉ , and a ⋅ y ˉ = a ⋅ ( a + p ) = wt a a\cdot\bar{y}=a\cdot(a+p)=\operatorname{wt}a a ⋅ y ˉ = a ⋅ ( a + p ) = wt a with p = y ˉ + a ∈ C p=\bar{y}+a\in C p = y ˉ + a ∈ C . So again t ≡ 1 t\equiv1 t ≡ 1 , with count 2 n − 1 + h [ y ˉ ∈ R ⊥ ] [ t ≡ 1 ] 2^{n-1+h}[\bar{y}\in R^\perp][t\equiv1] 2 n − 1 + h [ y ˉ ∈ R ⊥ ] [ t ≡ 1 ] .
Hence ν 8 ( 1 + 2 y ) = 2 n + h [ y ˉ ∈ R ⊥ ] [ t ≡ 1 ] \nu_8(1+2y)=2^{n+h}[\bar{y}\in R^\perp][t\equiv1] ν 8 ( 1 + 2 y ) = 2 n + h [ y ˉ ∈ R ⊥ ] [ t ≡ 1 ] and 2 3 k ν 8 = 2 5 k + h [ y ˉ ∈ R ⊥ ] [ t ≡ 1 ] 2^{3k}\nu_8=2^{5k+h}[\bar{y}\in R^\perp][t\equiv1] 2 3 k ν 8 = 2 5 k + h [ y ˉ ∈ R ⊥ ] [ t ≡ 1 ] .
Comparison. Let R R R be doubly even. Both t = 0 t=0 t = 0 (y = 0 y=0 y = 0 ) and t = 1 t=1 t = 1 (y = 2 e 1 y=2e_1 y = 2 e 1 ) occur with y ˉ = 0 ∈ R ⊥ \bar{y}=0\in R^\perp y ˉ = 0 ∈ R ⊥ . So (T) holds at all odd z z z iff [ t ≢ k ] = [ t ≡ 1 ] [t\not\equiv k]=[t\equiv1] [ t ≡ k ] = [ t ≡ 1 ] for both values of t t t , iff k k k is even:
given R doubly even, (T) holds at all odd z ⟺ k even . (11) \text{given }R\text{ doubly even, (T) holds at all odd }z\Longleftrightarrow k\text{ even}. \tag*{(11)} given R doubly even, (T) holds at all odd z ⟺ k even . (11)
Conclusion. ( ⇐ ) (\Leftarrow) ( ⇐ ) If k k k is even and R R R is doubly even, (T) holds at every z z z by § 5.2, (5.3.1) and (5.4.1), so P P P is formally self-dual. ( ⇒ ) (\Rightarrow) ( ⇒ ) Suppose P P P is formally self-dual; then (T) holds everywhere. If R R R were not doubly even, (5.3.1) fails; explicitly, take h ′ ∈ R h'\in R h ′ ∈ R with wt h ′ ≡ 2 ( m o d 4 ) \operatorname{wt}h'\equiv2\pmod4 wt h ′ ≡ 2 ( mod 4 ) and z = 2 h ~ ′ z=2\widetilde{h}' z = 2 h ′ : then Σ y = wt h ′ ≡ 2 \Sigma y=\operatorname{wt}h'\equiv2 Σ y = wt h ′ ≡ 2 , so F ( z ) = 0 F(z)=0 F ( z ) = 0 while ν 8 ( z ) = 2 3 k \nu_8(z)=2^{3k} ν 8 ( z ) = 2 3 k . So R R R is doubly even. If k k k were odd, (5.4.1) fails; explicitly, at z = 1 z=1 z = 1 (y = 0 y=0 y = 0 , t = 0 ≠ k t=0\ne k t = 0 = k ): ∣ F ( 1 ) ∣ 2 = 2 5 k + h |F(1)|^2=2^{5k+h} ∣ F ( 1 ) ∣ 2 = 2 5 k + h while ν 8 ( 1 ) = 0 \nu_8(1)=0 ν 8 ( 1 ) = 0 . So k k k is even, that is 4 ∣ n 4\mid n 4 ∣ n . □ \square □
Remark. For C = C ⊥ C=C^\perp C = C ⊥ one has R = C R=C R = C , h = k h=k h = k and ( C ∪ C ⊥ ) ∖ R = ∅ (C\cup C^\perp)\setminus R=\varnothing ( C ∪ C ⊥ ) ∖ R = ∅ ; the proof above is unchanged.
Status: reviewed, with 3 hostile reviews for the description of S S S and its formal self-duality, 2 for the graphs for m = 5 , 7 , 9 m=5,7,9 m = 5 , 7 , 9 and 3 for the construction that turns S S S into these graphs, which for m = 3 m=3 m = 3 (field F 8 \mathbb{F}_8 F 8 ) gives Gold’s x 3 x^3 x 3 graph up to translation and an orthogonal map. The instances for m = 11 , 13 m=11,13 m = 11 , 13 are exact computations, not reviewed.
For a code with 1 ∈ R 1\in R 1 ∈ R , as for 18.1, 28.1 and 30.1, the group H ′ H' H ′ is F 2 r + 2 \mathbb{F}_{2^{r+2}} F 2 r + 2 . For r = 4 , 6 , 8 r=4,6,8 r = 4 , 6 , 8 (m = r + 1 = 5 , 7 , 9 m=r+1=5,7,9 m = r + 1 = 5 , 7 , 9 ; r = 8 r=8 r = 8 is the case of 18.1), S S S is, up to a group isomorphism and a translation, the graph of the quadratic map ( x , α ) ↦ ( ( 1 + α ) x , q ( x ) ) (x,\alpha)\mapsto((1+\alpha)x,q(x)) ( x , α ) ↦ (( 1 + α ) x , q ( x )) on F 2 × F 2 \mathbb{F}_2\times\mathbb{F}_2 F 2 × F 2 , with q q q a non-degenerate quadratic form of Arf invariant 0, and it is primitive and formally self-dual in the finite-group sense of [KS]. For these three values, an F 2 \mathbb{F}_2 F 2 -linear identification (a written construction) turns S S S into a set { ( x , F ( x ) ) : x ∈ F 2 m } \{(x,F(x)):x\in\mathbb{F}_{2^m}\} {( x , F ( x )) : x ∈ F 2 m } with F F F a permutation, formally self-dual under the trace pairing ⟨ ( x , y ) , ( a , b ) ⟩ = ( − 1 ) Tr ( a x + b y ) \langle(x,y),(a,b)\rangle=(-1)^{\operatorname{Tr}(ax+by)} ⟨( x , y ) , ( a , b )⟩ = ( − 1 ) Tr ( a x + b y ) of [KS, § 6]. The step from S S S to the tables of F F F (§ 6.1) rests on that construction and on the program that built them; the formal self-duality of these tables was checked by exact integer computation on every character by two programs. The same construction, run at r = 10 r=10 r = 10 and r = 12 r=12 r = 12 (m = 11 , 13 m=11,13 m = 11 , 13 ) on the graph of the quadratic map above, gives permutations of F 2 11 \mathbb{F}_{2^{11}} F 2 11 and F 2 13 \mathbb{F}_{2^{13}} F 2 13 whose graphs are formally self-dual, checked by exact integer computation on every character (2 22 2^{22} 2 22 and 2 26 2^{26} 2 26 ): under the dot product by two programs written independently, each on the permutation it built, and, after transport to F 2 11 \mathbb{F}_{2^{11}} F 2 11 and F 2 13 \mathbb{F}_{2^{13}} F 2 13 through an orthonormal basis of the trace form, under the trace pairing by one of them. These permutations have algebraic degree 3 and are CCZ-equivalent to the quadratic map above (by construction: the identification is linear on the graph of the quadratic map). For r = 2 r=2 r = 2 , S S S is affinely equivalent to the example { ( x , x 3 ) : x ∈ F 8 } \{(x,x^3):x\in\mathbb{F}_8\} {( x , x 3 ) : x ∈ F 8 } of [KS]. The sets for m = 5 , 7 , 9 m=5,7,9 m = 5 , 7 , 9 are primitive and are not equivalent (in the sense of [LPS, Def. 2.17]) to the graph of a power map, to an affine graph, or to a non-trivial direct product. We point them out in connection with open question 3 of [KS], which asks for other formally self-dual sets of the form { ( x , F ( x ) ) } \{(x,F(x))\} {( x , F ( x ))} .
Explicit tables for the remark of § 6
Explicit instance, m = 5 m=5 m = 5 , field F 32 = F 2 [ x ] / ( x 5 + x 2 + 1 ) \mathbb{F}_{32}=\mathbb{F}_2[x]/(x^5+x^2+1) F 32 = F 2 [ x ] / ( x 5 + x 2 + 1 ) , elements written as integers 0 , … , 31 0,\ldots,31 0 , … , 31 in the polynomial basis:
F = [ 0 , 13 , 14 , 3 , 4 , 26 , 18 , 7 , 23 , 24 , 16 , 31 , 22 , 1 , 2 , 30 , 17 , 28 , 6 , 9 , 21 , 15 , 27 , 8 , 25 , 20 , 5 , 10 , 29 , 12 , 19 , 11 ] . F=[0,13,14,3,4,26,18,7,23,24,16,31,22,1,2,30,
17,28,6,9,21,15,27,8,25,20,5,10,29,12,19,11]. F = [ 0 , 13 , 14 , 3 , 4 , 26 , 18 , 7 , 23 , 24 , 16 , 31 , 22 , 1 , 2 , 30 , 17 , 28 , 6 , 9 , 21 , 15 , 27 , 8 , 25 , 20 , 5 , 10 , 29 , 12 , 19 , 11 ] .
For m = 7 m=7 m = 7 and m = 9 m=9 m = 9 the tables are available in coordinates where the trace pairing becomes the dot product, together with self-dual bases:
F 128 = F 2 [ x ] / ( x 7 + x + 1 ) \mathbb{F}_{128}=\mathbb{F}_2[x]/(x^7+x+1) F 128 = F 2 [ x ] / ( x 7 + x + 1 ) with basis [ 3 , 65 , 71 , 99 , 111 , 119 , 127 ] [3,65,71,99,111,119,127] [ 3 , 65 , 71 , 99 , 111 , 119 , 127 ] ;
F 512 = F 2 [ x ] / ( x 9 + x 4 + 1 ) \mathbb{F}_{512}=\mathbb{F}_2[x]/(x^9+x^4+1) F 512 = F 2 [ x ] / ( x 9 + x 4 + 1 ) with basis [ 3 , 17 , 23 , 27 , 60 , 263 , 354 , 424 , 494 ] [3,17,23,27,60,263,354,424,494] [ 3 , 17 , 23 , 27 , 60 , 263 , 354 , 424 , 494 ]
(Tr ( b i b j ) = δ i j \operatorname{Tr}(b_i b_j)=\delta_{ij} Tr ( b i b j ) = δ ij checked on all pairs). For m = 9 m=9 m = 9 one review derived the trace-pairing statement from the dot-product check and the self-dual basis; another review computed the [KS] criterion after transport through a self-dual basis, for m = 5 , 7 , 9 m=5,7,9 m = 5 , 7 , 9 . For m = 11 m=11 m = 11 and m = 13 m=13 m = 13 the tables (not reviewed, see § 6) can be regenerated by the program in the fields F 2 [ x ] / ( x 11 + x 2 + 1 ) \mathbb{F}_2[x]/(x^{11}+x^2+1) F 2 [ x ] / ( x 11 + x 2 + 1 ) and F 2 [ x ] / ( x 13 + x 4 + x 3 + x + 1 ) \mathbb{F}_2[x]/(x^{13}+x^4+x^3+x+1) F 2 [ x ] / ( x 13 + x 4 + x 3 + x + 1 ) , with a self-dual basis for the trace form (Tr ( b i b j ) = δ i j \operatorname{Tr}(b_i b_j)=\delta_{ij} Tr ( b i b j ) = δ ij checked); the program proves the irreducibility of both moduli.
Status
Labels: paper-proof (complete written proof), reviewed (paper proof plus hostile reviews by model instances that did not write it, see § 9 ; number given), certified (exact arithmetic, scope given), numerical (exact computation on a sample of cases, no general proof). The proofs, scripts and outputs behind each row are available on request.
The table gives one line per result. The list after it gives the sixteen claims behind it, each with what it does not establish; the row numbers in the table below refer to it.
Table 1 (PDF p. 18).
Row 1. Statement: Theorem A, items 1, 2, 4 (finite pair, sizes, ν T \nu_T ν T values). Label and exact scope: reviewed (2 hostile reviews, one of which re-derived the result from the statement alone; also the two GPT-6 Astra reviews, see § 9 ). Certified for n = 18 n = 18 n = 18 on all $2^{18}$ characters and n = 28 , 30 n = 28, 30 n = 28 , 30 on all 2 26 2^{26} 2 26 by two independent programs on the codes of our earlier computations (first: Walsh transform and pair counting, direct sums on all characters at n = 18 n = 18 n = 18 , on 4096 random characters at $n = 28, 30; second: exact transform in Z [ ζ 8 ] \mathbb{Z}[\zeta_8] Z [ ζ 8 ] on all characters), the
second also on the codes extracted from the entries of [RP]; exhaustive n ≤ 6 n \le6 n ≤ 6 (1380 codes at n = 6 n = 6 n = 6 ); 483 codes n = 10 n = 10 n = 10 –16; 78 random codes k = 2..8 k = 2..8 k = 2..8 . Not established: no check of the proof by a person; among the two hostile reviews, § 3.6 (b), (c) and § 3.10 (ii) were redone by one only (and by the Astra review); pairs C 2 ′ ⊆ C 2 ⊥ C'_2 \subseteq C^\perp_2 C 2 ′ ⊆ C 2 ⊥ ; odd n n n ; a necessary condition.
Row 2. Statement: Theorem A, item 3 (formal duality in R n \mathbb{R}^n R n , Q = A ∗ + T / 8 Q = A^* + T/8 Q = A ∗ + T /8 ). Label and exact scope: reviewed (2 hostile reviews: one of the two of row 1, and one on item 3 alone with items 1, 2, 4 admitted; the other review of row 1 took this step from them; also the GPT-6 Astra reviews, § 9); paper step via CKRS Cor. 2.7, not machine-checked. Not established: nothing identified.
Row 4. Statement: For 1 ∈ R 1 \in R 1 ∈ R , r r r even ≥ 4 \ge4 ≥ 4 : pair is no LPS / KS example and no direct product. Label and exact scope: reviewed (1 hostile review), in this restricted form. Not established: the list of [LPS] pairs in 2-groups that the argument uses (including their sporadic pair in Z 2 × Z 2 4 \mathbb{Z}_2 \times\mathbb{Z}_2^4 Z 2 × Z 2 4 and their computer lists for ∣ G ∣ ≤ 63 \lvert G\rvert\le63 ∣ G ∣ ≤ 63 ) has not been reviewed since it was completed; the one review counted in the label found that list incomplete before it was completed; the infinite families that LPS attribute to other work (extending their sporadic example) were not read for this row; 1 ∉ R 1 \notin R 1 ∈ / R , r ≥ 2 r \ge2 r ≥ 2 not compared with LPS.
Row 5. Statement: r = 1 r = 1 r = 1 : equivalent to TITO × \times × TITO; r = 2 r = 2 r = 2 , 1 ∈ R 1 \in R 1 ∈ R : S S S , T T T each affinely equivalent to Gold in F 2 8 \mathbb{F}_2^8 F 2 8 . Label and exact scope: r = 1 r = 1 r = 1 : numerical, 20/20 codes, plus an explicit automorphism; r = 2 r = 2 r = 2 : certified per instance, 12/12 and 18/18 codes. Not established: a common isomorphism for the pair at r = 2 r = 2 r = 2 .
Row 6. Statement: No Theorem A pair with r ≥ 2 r \ge2 r ≥ 2 comes from a Li–Pott construction. Label and exact scope: paper-proof plus exact checks. Not established: product route for 1 ∉ R 1 \notin R 1 ∈ / R , r ≥ 4 r \ge4 r ≥ 4 and 1 ∈ R 1 \in R 1 ∈ R , r r r even ≥ 6 \ge6 ≥ 6 .
Row 7. Statement: Proposition I, items 1, 2. Label and exact scope: reviewed (3 hostile reviews; the text repaired after them was reviewed again). Certified for n ≤ 6 n \le6 n ≤ 6 (all codes n ≤ 4 n \le4 n ≤ 4 , 21 permutation classes at n = 6 n = 6 n = 6 ); 4 507 instances n = 2..16 n = 2..16 n = 2..16 . Not established: nothing identified.
Row 8. Statement: Proposition I, item 3: Γ / ( 2 2 ) \Gamma/(2\sqrt{2}) Γ/ ( 2 2 ) formally isodual. Label and exact scope: reviewed (3 hostile reviews, as row 7), conditional on Theorem A item 3. Not established: nothing identified (formal self-duality for 18, 28, 30: row 9).
Row 9. Statement: Remark of § 2.4: P P P formally self-dual if and only if 4 ∣ n 4 \mid n 4 ∣ n and R R R doubly even; hence 18.1, 28.1, 30.1 not formally self-dual. Label and exact scope: reviewed (3 hostile reviews; only if without Theorem A; if through Theorem A item 3 and Proposition I in all three reviews, by a direct proof in the second and third; the third redid both directions without Theorem A, by an argument that does not use C ≠ C ⊥ C \ne C^\perp C = C ⊥ ). Certified by exact computation on every [ n , n / 2 ] [n,n/2] [ n , n /2 ] code for n ≤ 8 n \le8 n ≤ 8 and on random and forced codes up to n = 16 n = 16 n = 16 . Not established: for 18.1, 28.1, 30.1: the identification of the codes of row 10 (two programs, which give the same hull weights; set equality in the second rests on an L ′ L' L ′ -periodicity argument (item 1 of Theorem A states this) plus a sample).
Row 10. Statement: Entries 18.1, 28.1, 30.1 equal Γ ( C , C ⊥ ) / 8 \Gamma(C,C^\perp)/\sqrt{8} Γ ( C , C ⊥ ) / 8 after sign changes and a translation; hulls 1, 2, 3; 1 ∈ R 1 \in R 1 ∈ R ; d = 6 , 8 , 8 d = 6, 8, 8 d = 6 , 8 , 8 . Label and exact scope: certified by two independent programs, all three programs (first: lattice equality; second: membership of every translate and a density identity). Not established: in the second program, set equality rests on a short paper argument that Γ \Gamma Γ is L ′ L' L ′ -periodic (item 1 of Theorem A states this), tested on a sample of points; equivalence of the codes with Bierbrauer–Edel’s printed codes (only equal weight enumerators).
Row 11. Statement: The duals of the earlier note [EN] are, at unit density, isometric to the packings 18.1, 28.1, 30.1. Label and exact scope: certified by two independent exact programs (signs + translation in the code frame; point-set isometry in the coordinates of [RP], all 512 / 8192 / 8192 translates); the T T T files and the certificates of formal duality of [EN] are not part of this deposit. Not established: both read the T T T files of the earlier note the same way; that reading is validated by the identities (all characters in the first program; all at n = 18 n = 18 n = 18 , 400 samples at n = 28 , 30 n = 28, 30 n = 28 , 30 in the second), not against the producing code; whether the T T T of the earlier note equals the formula T T T up to isometry.
Row 12. Statement: d min 2 ( Γ ) = 24 , 32 , 32 d_{\min}^{2}(\Gamma) = 24, 32, 32 d m i n 2 ( Γ ) = 24 , 32 , 32 ; on the coordinates of [RP] at unit density 3, 4, 4. Label and exact scope: paper-proof lemma (for 1 ∈ R 1 \in R 1 ∈ R ) plus exact enumeration of d , d ′ d, d' d , d ′ (one program, agrees with a second); on the coordinates of [RP]: all 512 base points at n = 18 n = 18 n = 18 , four base points at n = 28 n = 28 n = 28 , one at n = 30 n = 30 n = 30 . Not established: exhaustive pair search at n ≥ 18 n \ge18 n ≥ 18 .
Row 13. Statement: Stealth radius at unit density of the duals of the earlier note [EN] = d min ( Γ ) / ( 2 2 ) = 3 , 2 , 2 = d_{\min}(\Gamma)/(2\sqrt{2}) = \sqrt{3}, 2, 2 = d m i n ( Γ ) / ( 2 2 ) = 3 , 2 , 2 . Label and exact scope: paper-proof: for the dual given by formula (2), conditional on Theorem A item 3, with CCV § 5.1; for the duals of the earlier note [EN], through the computer-certified isometry of Row 11 (§ 8.3), or from the certificates of formal duality in that note (stated there, not proved here) and CCV § 5.1. Not established: any optimality; comparison with non-lattice configurations other than those of Cohn’s table of stealth radius records [ST].
Row 14. Statement: Remark of § 6: graphs for m = 5 , 7 , 9 m = 5, 7, 9 m = 5 , 7 , 9 formally self-dual under the trace pairing; same for the computed instances m = 11 , 13 m = 11, 13 m = 11 , 13 . Label and exact scope: certified on every character (1024, 16384, 262144) by two programs; reviewed (2 hostile reviews); the construction from S S S to the tables: reviewed (3 hostile reviews); tables built by one program. m = 11 , 13 m = 11, 13 m = 11 , 13 : certified on every character (2 22 2^{22} 2 22 , 2 26 2^{26} 2 26 ), dot product by two programs written independently (each on its own permutation), trace pairing by one program; not reviewed. Not established: the step from S S S to the tables beyond that construction and that program; for m = 3 m = 3 m = 3 the construction gives Gold’s x 3 x^3 x 3 graph up to translation and an orthogonal map, hence no example beyond [KS] there; the general family is not claimed here (trace-pairing graphs for r ≥ 14 r \ge14 r ≥ 14 not computed); for m = 11 , 13 m = 11, 13 m = 11 , 13 , a second program for the trace pairing, and the comparisons of row 15; prior work: see § 10.2.
Row 15. Statement: Remark of § 6: S S S for r = 2 r = 2 r = 2 affinely equivalent to KS’s x 3 x^3 x 3 on F 8 \mathbb{F}_8 F 8 ; m = 5 , 7 , 9 m = 5, 7, 9 m = 5 , 7 , 9 sets not equivalent to power maps, affine graphs or products. Label and exact scope: certified (spectra, explicit equivalences) plus paper-proof (product exclusion); reviewed (2 hostile reviews). Not established: prior work: not found in the sources of § 10.2, which also lists the sources not reached.
Computations, comparison with known pairs, and the configurations of the earlier note
What is computed
For n = 18 , 28 , 30 n = 18, 28, 30 n = 18 , 28 , 30 both identities of item 2 were checked on every character (2 18 2^{18} 2 18 , 2 26 2^{26} 2 26 , 2 26 2^{26} 2 26 ) by two independent programs on the codes of our earlier computations. The first uses a Walsh transform and pair counting, with direct character sums on every character at n = 18 n = 18 n = 18 and on 4096 random characters at n = 28 , 30 n = 28, 30 n = 28 , 30 . The second uses an exact transform in Z [ ζ 8 ] \mathbb{Z}[\zeta_{8}] Z [ ζ 8 ] on every character and counts differences directly; it was also run on the codes extracted from the coordinates of [RP] (entries 18.1, 28.1, 30.1; hull dimensions 1, 2, 3; d ( C ) = d ( C ⊥ ) = 6 , 8 , 8 d(C)=d(C^\perp)=6,8,8 d ( C ) = d ( C ⊥ ) = 6 , 8 , 8 ). Here H ′ ≅ F 2 26 H' \cong\mathbb{F}_2^{26} H ′ ≅ F 2 26 and ∣ S ∣ = ∣ T ∣ = 512 , 8192 , 8192 |S|=|T|=512,8192,8192 ∣ S ∣ = ∣ T ∣ = 512 , 8192 , 8192 . The ν T \nu_T ν T histograms are { 0 : 195587 , 2 : 65536 , 128 : 1020 , 512 : 1 } \{0:195587, 2:65536, 128:1020, 512:1\} { 0 : 195587 , 2 : 65536 , 128 : 1020 , 512 : 1 } in dimension 18 and { 0 : 50315267 , 2 : 16777216 , 2048 : 16380 , 8192 : 1 } \{0:50315267, 2:16777216, 2048:16380, 8192:1\} { 0 : 50315267 , 2 : 16777216 , 2048 : 16380 , 8192 : 1 } in dimensions 28 and 30, as item 4 predicts for r = 8 , 12 , 12 r=8,12,12 r = 8 , 12 , 12 . Negative controls fail as they should: with ε \varepsilon ε flipped, the first identity fails on half of the characters; with one element of T T T moved, the second identity fails at every non-zero group element. On small codes: an exhaustive exact search for n = 2 , 4 , 6 n=2,4,6 n = 2 , 4 , 6 (all 1380 codes at n = 6 n=6 n = 6 ), 483 codes for n = 10 n=10 n = 10 to 16, and 78 random codes with k = 2 , … , 8 k=2,\ldots,8 k = 2 , … , 8 , all passing. Item 3 is a paper step (CKRS Cor. 2.7) and was not machine-checked.
Position with respect to known finite pairs
For 1 ∈ R 1\in R 1 ∈ R and r r r even ≥ 4 \ge4 ≥ 4 , which covers 18.1, 28.1, 30.1 (r = 8 , 12 , 12 r=8,12,12 r = 8 , 12 , 12 ), the finite pair is neither one of the examples of Li–Pott–Schüler [LPS] or Kölsch–Schüler [KS] nor a direct product of formally dual pairs: ν T \nu_T ν T takes the value 2, while a product of non-trivial factors in elementary 2-groups only takes values ≥ 4 \ge4 ≥ 4 off 0. For r = 1 r=1 r = 1 the finite pair is equivalent to a product of two TITO pairs [CKRS] (20 of 20 codes checked); for r = 2 r=2 r = 2 with 1 ∈ R 1\in R 1 ∈ R , S S S and T T T are each affinely equivalent to the Gold graph { ( x , x 3 ) } ⊂ F 2 8 \{(x,x^3)\}\subset\mathbb{F}_2^8 {( x , x 3 )} ⊂ F 2 8 of [KS] (checked on samples). No pair with r ≥ 2 r\ge2 r ≥ 2 comes from the Li–Pott constructions [LP1, LP2], whose groups have order 2 4 m + 1 2^{4m+1} 2 4 m + 1 and whose pairs have ∣ T ∣ = 2 ∣ S ∣ |T|=2|S| ∣ T ∣ = 2∣ S ∣ .
What it means for the configurations of the earlier note
The entries 18.1, 28.1 and 30.1 of [RP] are, after sign changes of coordinates and a translation, exactly Γ ( C , C ⊥ ) / 8 \Gamma(C,C^\perp)/\sqrt{8} Γ ( C , C ⊥ ) / 8 for binary [ n , n / 2 ] [n,n/2] [ n , n /2 ] codes C C C with hull dimensions 1, 2, 3 and 1 ∈ R 1\in R 1 ∈ R (exact check on all translates by two independent programs; in the second, equality of the sets, beyond the membership of every translate, rests on a short argument that Γ \Gamma Γ is periodic under the lattice L ′ L' L ′ of Theorem A (item 1 of Theorem A states this), tested on a sample of points). Proposition I therefore applies to them. Independently of that chain, we compared the dual configurations Q Q Q rebuilt from the files of T T T of the earlier note [EN], not part of this deposit and given there for the packings of [RP], by two independent exact programs: one finds a map of sign changes and a translation from the 8 Q 8Q 8 Q of the earlier note onto Γ ( C , C ⊥ ) \Gamma(C,C^\perp) Γ ( C , C ⊥ ) ; the other, working on point sets in the Gram coordinates of [RP], finds an explicit isometry at scale factor 1 between the packing at unit density and the dual of the earlier note, and recovers the contact numbers 3264, 71400 and 59340 of [RP]. So, at unit density, the dual configurations of the earlier note are isometric copies of the record packings themselves, which are Biebräuer–Edel packings Γ ( C , C ⊥ ) \Gamma(C,C^\perp) Γ ( C , C ⊥ ) . Both programs read the files of T T T of the earlier note the same way, and that reading is validated by the duality identities, not by comparison with the code that produced the files.
Minimal distances
For the three codes, d min 2 ( Γ ) = 24 , 32 , 32 d_{\min}^2(\Gamma)=24,32,32 d m i n 2 ( Γ ) = 24 , 32 , 32 : for 1 ∈ R 1\in R 1 ∈ R , min ( 4 d , 4 d ′ , 32 , n + 8 ) ≤ d min 2 ( Γ ) ≤ min ( 4 d , 4 d ′ , 32 ) \min(4d,4d',32,n+8)\le d_{\min}^2(\Gamma)\le\min(4d,4d',32) min ( 4 d , 4 d ′ , 32 , n + 8 ) ≤ d m i n 2 ( Γ ) ≤ min ( 4 d , 4 d ′ , 32 ) , with d = d ′ = 6 , 8 , 8 d=d'=6,8,8 d = d ′ = 6 , 8 , 8 and explicit pairs of points at these distances. On the coordinates of [RP] at unit density the minimal squared distances are 3, 4, 4 (enumerated from all 512 base points in dimension 18, from four base points in dimension 28 and from one base point in dimension 30). The radii 3 , 2 , 2 \sqrt{3},2,2 3 , 2 , 2 of the earlier note [EN] are therefore the minimal distances of the packings at unit density, restated; the comparison with duals of lattices made there is a comparison of center densities. For the dual given by formula (2) , this step depends on Theorem A, item 3, with [CCV, § 5.1]; for the duals of the earlier note [EN], it follows from the isometry above, or from the certificates of formal duality in that note (stated there, not proved here) and [CCV, § 5.1].
Proof of the bounds. Here d = d ( C ) d = d(C) d = d ( C ) and d ′ = d ( C ⊥ ) d' = d(C^\perp) d ′ = d ( C ⊥ ) are the minimum weights, and 1 ∈ R \mathbf{1} \in R 1 ∈ R , so C C C and C ⊥ C^\perp C ⊥ are even. Let x ≠ x ′ x \ne x' x = x ′ be points of Γ \Gamma Γ .
Both in E E E ( x = − 2 b ~ + 4 c ~ + 8 Z n , x ′ = − 2 b ~ ′ + 4 c ~ ′ + 8 Z n ) (x = -2\widetilde{b} + 4\widetilde{c} + 8\mathbb{Z}^n,\ x' = -2\widetilde{b}' + 4\widetilde{c}' + 8\mathbb{Z}^n) ( x = − 2 b + 4 c + 8 Z n , x ′ = − 2 b ′ + 4 c ′ + 8 Z n ) . If b ≠ b ′ b \ne b' b = b ′ , then b + b ′ b + b' b + b ′ is a non-zero word of C C C , so at least d d d coordinates of x − x ′ x - x' x − x ′ are ≡ 2 ( m o d 4 ) \equiv2 \pmod{4} ≡ 2 ( mod 4 ) , and ∣ x − x ′ ∣ 2 ≥ 4 d \lvert x - x'\rvert^2 \ge4d ∣ x − x ′ ∣ 2 ≥ 4 d . If b = b ′ b = b' b = b ′ and c ≠ c ′ c \ne c' c = c ′ , then c + c ′ c + c' c + c ′ is a non-zero word of even weight, so at least two coordinates are ≡ 4 ( m o d 8 ) \equiv4 \pmod{8} ≡ 4 ( mod 8 ) , and ∣ x − x ′ ∣ 2 ≥ 2 ⋅ 16 = 32 \lvert x - x'\rvert^2 \ge2 \cdot16 = 32 ∣ x − x ′ ∣ 2 ≥ 2 ⋅ 16 = 32 . If b = b ′ b = b' b = b ′ and c = c ′ c = c' c = c ′ , then x − x ′ ∈ 8 Z n x - x' \in8\mathbb{Z}^n x − x ′ ∈ 8 Z n and ∣ x − x ′ ∣ 2 ≥ 64 \lvert x - x'\rvert^2 \ge64 ∣ x − x ′ ∣ 2 ≥ 64 .
Both in O O O : the same argument with C ⊥ C^\perp C ⊥ gives ∣ x − x ′ ∣ 2 ≥ min ( 4 d ′ , 32 ) \lvert x - x'\rvert^2 \ge\min(4d', 32) ∣ x − x ′ ∣ 2 ≥ min ( 4 d ′ , 32 ) .
One in each half: all coordinates of x − x ′ x - x' x − x ′ are odd, so ∣ x − x ′ ∣ 2 ≥ n \lvert x - x'\rvert^2 \ge n ∣ x − x ′ ∣ 2 ≥ n and ∣ x − x ′ ∣ 2 ≡ n ( m o d 8 ) \lvert x - x'\rvert^2 \equiv n \pmod{8} ∣ x − x ′ ∣ 2 ≡ n ( mod 8 ) . Equality ∣ x − x ′ ∣ 2 = n \lvert x - x'\rvert^2 = n ∣ x − x ′ ∣ 2 = n would need every coordinate ≡ ± 1 ( m o d 8 ) \equiv\pm1 \pmod{8} ≡ ± 1 ( mod 8 ) . Write x = 1 − 2 a ~ + 4 c ~ x = \mathbf{1} - 2\widetilde{a} + 4\widetilde{c} x = 1 − 2 a + 4 c ( a ∈ C ⊥ , wt c odd ) (a \in C^\perp,\ \operatorname{wt} c\ \text{odd}) ( a ∈ C ⊥ , wt c odd ) and x ′ = − 2 b ~ + 4 c ~ ′ x' = -2\widetilde{b} + 4\widetilde{c}' x ′ = − 2 b + 4 c ′ ( b ∈ 1 + C , wt c ′ even ) (b \in\mathbf{1} + C,\ \operatorname{wt} c'\ \text{even}) ( b ∈ 1 + C , wt c ′ even ) . Coordinate i i i of x − x ′ x - x' x − x ′ is ≡ 1 + 2 ( b i − a i ) + 4 ( c i − c i ′ ) \equiv1 + 2(b_i - a_i) + 4(c_i - c'_i) ≡ 1 + 2 ( b i − a i ) + 4 ( c i − c i ′ ) , and it is ± 1 \pm1 ± 1 iff c i + c i ′ ≡ b i ( 1 − a i ) ( m o d 2 ) c_i + c'_i \equiv b_i(1 - a_i) \pmod{2} c i + c i ′ ≡ b i ( 1 − a i ) ( mod 2 ) . Summing over i i i gives wt ( c + c ′ ) ≡ wt b − ∣ a ∩ b ∣ ( m o d 2 ) \operatorname{wt}(c + c') \equiv\operatorname{wt} b - \lvert a \cap b\rvert\pmod{2} wt ( c + c ′ ) ≡ wt b − ∣ a ∩ b ∣ ( mod 2 ) . The left side is odd. The right side is even: wt b = n − wt ( b + 1 ) \operatorname{wt} b = n - \operatorname{wt}(b + \mathbf{1}) wt b = n − wt ( b + 1 ) is even because b + 1 ∈ C b + \mathbf{1} \in C b + 1 ∈ C is even, and ∣ a ∩ b ∣ ≡ a ⋅ b = a ⋅ 1 + a ⋅ ( b + 1 ) = 0 \lvert a \cap b\rvert\equiv a \cdot b = a \cdot\mathbf{1} + a \cdot(b + \mathbf{1}) = 0 ∣ a ∩ b ∣ ≡ a ⋅ b = a ⋅ 1 + a ⋅ ( b + 1 ) = 0 . This is a contradiction, so ∣ x − x ′ ∣ 2 ≥ n + 8 \lvert x - x'\rvert^2 \ge n + 8 ∣ x − x ′ ∣ 2 ≥ n + 8 .
Upper bounds: the points − 2 ⋅ 1 -2 \cdot\mathbf{1} − 2 ⋅ 1 and − 2 ( 1 + c ~ min ) -2(\mathbf{1} + \widetilde{c}_{\min}) − 2 ( 1 + c m i n ) of E E E ( c min ∈ C (c_{\min} \in C ( c m i n ∈ C of weight d ) d) d ) differ by a vector of squared norm 4 d 4d 4 d . The points 1 + 4 e 1 \mathbf{1} + 4e_1 1 + 4 e 1 and 1 − 2 d ~ min + 4 e 1 \mathbf{1} - 2\widetilde{d}_{\min} + 4e_1 1 − 2 d m i n + 4 e 1 of O O O ( d min ∈ C ⊥ (d_{\min} \in C^\perp ( d m i n ∈ C ⊥ of weight d ′ ) d') d ′ ) differ by a vector of squared norm 4 d ′ 4d' 4 d ′ . The points − 2 ⋅ 1 -2 \cdot\mathbf{1} − 2 ⋅ 1 and − 2 ⋅ 1 + 4 ( e 1 + e 2 ) -2 \cdot\mathbf{1} + 4(e_1 + e_2) − 2 ⋅ 1 + 4 ( e 1 + e 2 ) of E E E differ by a vector of squared norm 32 32 32 . For n = 18 , 28 , 30 n = 18, 28, 30 n = 18 , 28 , 30 : min ( 4 d , 4 d ′ , 32 , n + 8 ) = min ( 4 d , 4 d ′ , 32 ) = 24 , 32 , 32 \min(4d, 4d', 32, n + 8) = \min(4d, 4d', 32) = 24, 32, 32 min ( 4 d , 4 d ′ , 32 , n + 8 ) = min ( 4 d , 4 d ′ , 32 ) = 24 , 32 , 32 .
Formal self-duality, as opposed to isoduality
If 4 ∣ n 4 \mid n 4 ∣ n and R R R is doubly even, D = 0 D = 0 D = 0 is admissible and P P P is formally self-dual. For the three record packings the condition fails: n / 2 n/2 n /2 is odd for n = 18 n = 18 n = 18 and 30 30 30 , and for n = 28 n = 28 n = 28 the hull is not doubly even (basis weights 14, 14). Since formal duals are not unique, this failure alone would not exclude formal self-duality; the only if direction of the remark of § 2.4 does.
Context: the densest packings and formal duality
Cohen, Cohn and Viazovska write: “We see no reason why the densest sphere packing should even have a formal dual” [CCV, § 1, line 96 of the source of arXiv:2609.03121v1].
The packings 18.1, 28.1 and 30.1 are the densest known in their dimensions; none is proved to be the densest. In Cohn’s table of sphere packing density bounds, read on 17 November 2026 at https://cohn.mit.edu/sphere-packing , the best upper bound in dimensions 18, 28 and 30 exceeds their density by the factors 2.121, 4.507 and 10.91 printed there. Their formal isoduality therefore says nothing about the densest packing in these dimensions, which is unknown.
Tool and computational resource disclosure
The work for Theorem A, Proposition I and the remarks was done between 16 and 18 November 2026. Agents run in Claude Code did it. The Astra reviews were run through Codex. The codes and certificates of the earlier note predate this work.
Antoine Olivier read the statements of this note and redid the example of § 2.5 by hand; he did not check the proofs. The decision to pursue this family and the decision to submit it for deposit are Antoine Olivier’s.
Search, computation, proofs, the reviews other than Astra’s and Gemini’s, and this draft were produced by AI agents (Anthropic Claude models, Opus-, Sonnet- and Fable-class). They asked him multiple-choice questions along the way.
On 18 November, Theorem A was also reviewed by GPT-6 Astra (OpenAI). The first review was an attack from the statement, without the proof. The statement given to it cited two earlier reviews; a second attack, from a copy of the statement without them, reached the same conclusions. The second review was line by line and had read the first. Both found the five items true. Item 4 was read as counting disjoint families, and item 1 half by half; the wording of items 1 and 4 above follows its corrections. Its other two reservations concerned the report of the second computer check of § 8.1 . That report has since been repaired; the repair was re-read once by a Claude reviewer, not by Astra. The two reservations did not concern the proof.
On 18 November, before the last corrections of wording, Gemini 4 Carbon (Google), run through OpenRouter, read the whole note once from the PDF as a hostile referee. It judged Theorem A, Proposition I, the remark on formal self-duality and every lemma of §§ § 3 and § 8.4 correct, and found nothing fatal or serious. A Claude model checked its minor findings; the one that needed a change, a congruence mod 2 in § 8.4 , is applied. Its report stops partway through its hand check of the tables of § 6.1 .
The hostile reviews cited in the table were made by fresh model instances that did not write the proofs. They were not human referees. No human has checked the proofs yet.
The proofs in §§ § 3 to § 5 and the proof of the lemma in § 8.4 were rewritten from the proofs that these reviews read. This rewritten text has not itself been reviewed by a hostile reviewer; one model reviewer compared it with the reviewed proofs and redid the computations without a program. The remark at the end of § 3.14 (last line of Theorem A: r r r is even when 1 ∈ R 1 \in R 1 ∈ R ) was not reviewed.
All computations ran on a local PC in exact integer or rational arithmetic. The scripts and outputs are kept and available on request.
Limits
Two readings of Bierbrauer–Edel 2000
The definition of the packing on p. 97 of [BE] puts the cosets 1 + C 2 1 + C_2 1 + C 2 in the even type and C 2 ′ C'_2 C 2 ′ in the odd type; the table in the proof of Theorem 1, p. 98, uses the opposite assignment. The minimal-distance formula printed in Theorem 1 agrees with the p. 98 reading on every orthogonal pair we enumerated (all pairs of linear codes at n = 5 n = 5 n = 5 (5769) and n = 6 n = 6 n = 6 (95706), and 1920 sampled pairs for n = 7 n = 7 n = 7 to 10). For the p. 97 reading (all 102 069 orthogonal pairs with n ≤ 6 n \le6 n ≤ 6 , and 1920 sampled pairs for n = 7 n = 7 n = 7 to 10), the term n + 8 \sqrt{n+8} n + 8 is attained exactly when n n n is even and both codes are even, and is n \sqrt{n} n otherwise; for Γ ( C , C ′ ) \Gamma(C,C') Γ ( C , C ′ ) this condition is 1 ∈ R 1 \in R 1 ∈ R . For the p. 97 reading this is also derived on paper. Non-linear codes, which [BE] allow, were not tested. Theorem A and Proposition I are stated for the p. 97 reading, formula (1). For 1 ∈ R 1 \in R 1 ∈ R , which covers 18.1, 28.1 and 30.1, the two readings give the same packing up to translation and exchange of the codes (27 of 27 cases tested), and the entries of [RP] were matched directly to formula (1). For 1 ∉ R 1 \notin R 1 ∈ / R , Theorem A concerns the configuration (1), which may differ from the packing of the p. 98 reading.
Prior art
For Theorem A, three rounds of search (16 November 2026) in zbMATH Open, Crossref, OpenAlex and the arXiv API, plus web searches, found no source giving a formal dual of Γ ( C , C ′ ) \Gamma(C,C') Γ ( C , C ′ ) or implying one; Semantic Scholar was rate-limited. For Proposition I, three rounds (17 November 2026) in OpenAlex and Semantic Scholar (works citing [CKS], [CKRS], [BE] and [V99]), the arXiv API, zbMATH Open, web search and MathOverflow titles found no statement that the Bierbrauer–Edel or Vardy configurations built on ( C , C ⊥ ) (C,C^{\perp}) ( C , C ⊥ ) are formally isodual or formally self-dual. The closest work in both searches is [CCV, § 5], which constructs a formal dual of Vardy’s 20-dimensional packing, a different configuration with 16 translates against the packing’s 4. Not read: the full text of [BE] beyond pp. 97–98, [V95] and [V99], [SPLAG], [CS94] in full; Google Scholar, MathSciNet and Crossref were not queried for Proposition I; the November 2026 preprint on dimensions 10–12 listed in Cohn’s table of stealth radius records [ST] was not read. These are statements of the form not found in the sources listed, not of absence.
For the remark of § 6: full texts of the theses of Schüler and Kölsch extracted and searched by regular expressions (formulas not re-read on the page images; Kölsch’s thesis only partly extracted, read by grep), and the works citing [KS] in OpenAlex, Semantic Scholar and OpenCitations (two; the second, a bibliography list, not read): not found in these sources; not reached: Google Scholar, the Springer page of [KS], the text of the 36 references of [KS], the WCC/SETA/BFA proceedings, the personal pages of Schüler, Li and Pott, possible Master’s or habilitation theses (not searched). Literature after [KS] beyond these searches is not covered.
What this note does not claim
A change of the values in dimensions 18, 28 and 30 of Cohn’s table of stealth radius records [ST]: for the dual given by the formula of Theorem A, by [CCV, § 5.1] and Theorem A, item 3; for the duals of the earlier note [EN], through § 8.3 , or by its certificates of formal duality (stated there, not proved here) and [CCV, § 5.1]; in both cases the radii are the packings’ minimal distances at unit density, and only their description changes.