Tiles without spectra in abelian 2-groups: a smaller elementary abelian example, exact orthogonality defects, and the optimality of a fibre–clique certificate
Abstract
Fan and Kadir have refuted the statement — formulated explicitly by Malikiosis and attributed by him to Shi — that every translational tile in a finite abelian p-group is spectral, by exhibiting three explicit tiles without spectra: a 64-point set Γ in Zm4⁴ × Zm2², a 512-point set R₂ in 𝔽₂¹³, and a 2187-point set in 𝔽₃⁹. This paper is about the first two of them. We give a smaller counterexample. Carrying out, on the authors' own base data, the second of the two routes to smaller examples that they name in their concluding remarks — "reduce the number of layer types while forcing the weighted horizontal Fourier zero graph to have clique number below the complement size" — produces a 128-point translational tile of the elementary abelian group 𝔽₂¹¹, of order 2048, with a 16-point tiling complement and no spectrum: the dimension drops from 13 to 11 and the ambient order from 8192 to 2048. We also show that it is the base tile, and not the choice of layer complements, that limits this method. The common Fourier zero set carrying the binary certificate is exactly the set of nonzero frequencies at which the Fourier transform of the base tile A₂ does not vanish; consequently the relevant clique number is at least 12 for every choice of tiling complements of A₂ and every layer group, so the authors' certificate is optimal for their base, with a slack of exactly 4 against the complement size 16. Two quantitative additions accompany these. Non-spectrality asserts only that |A| pairwise orthogonal characters do not exist; we compute the exact maximum in three cases — 48 of the 64 for Γ, 384 of 512 for R₂, and 96 of 128 for the new example. And for the exponent-4 example we show that its one search — that a 16-point set K does not tile H=Zm4⁴ × Zm2 — cannot be traded for a certificate of the only shape a general argument offers: a tiling complement of K is an independent set of Cay(H,(K-K)setminus{0}), so the clique–coclique bound |C| |S| ≤ |H| turns any 17-point clique of that graph into a search-free refutation of the tiling, and we prove that its clique number is exactly 16, attained by K itself. The bound then gives |S| ≤ 32, exactly the size a tiling complement has, so it has no slack. Every theorem below is machine-checked in Lean 4; the clique numbers that are reported as measurements are marked as such and are not part of the formal development.
Open review
This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.
Archived files
- Version 2 · current (opens in a new tab)
Source snapshot 2026-09-07 03:53 UTC
File fingerprint
469c094637f5d6cd8db2a49d1be52478ebde52923bfe653076bf20768012f986
Claim ledger
Stated results
fp-1known data2026-09-03
The source's Appendix A data, mechanically transcribed: |K| = |E| = 16, |T₀| = |T₁| = 32, |Gamma| = 64, |E x 0| = 16, and the pairing on Z₄⁴ x Z₂² is nondegenerate
fp-2known data2026-09-03
Gamma tiles Z₄⁴ x Z₂² with complement E x 0: the tiling half of the source's Theorem 1.2(1)
fp-3known data2026-09-03
K does not tile H = Z₄⁴ x Z₂: the source's Proposition 5.1(3), by an exhaustive exact cover whose search procedure is proved complete inside Lean
fp-4routine2026-09-03
Every nonzero difference of K, put in layer 0, is a Fourier NON-zero of Gamma – checked directly on Gamma, which is the only consequence of the source's Proposition 5.1(4) that the argument uses
fp-5known data2026-09-03
Gamma has no spectrum: no 64 characters of Z₄⁴ x Z₂² are pairwise orthogonal on Gamma (the non-spectrality half of the source's Theorem 1.2(1))
fp-6known data2026-09-03
Malikiosis, Conjecture 1.3 ('T-S holds in every finite Abelian p-group') is false: the abelian 2-group Z₄⁴ x Z₂² of order 1024 carries a translational tile that is not spectral
fp-7known data2026-09-03
The source's Proposition 5.1(1): E is a spectrum of K in H, i.e. the Gram matrix of (i^(<k,e>)) is 16 I₁6
fp-8known data2026-09-03
The source's Proposition 5.1(2): E + T₀ = H and E + T₁ = H
fp-9known data2026-09-03
The source's Proposition 5.1(4) and its printed 'oriented_differences=152': |(K-K){0| = 152 and |1hat_(T₀)(d)|²!= |1hat_(T₁)(d)|² for every one of them
fp-10routine2026-09-03
The clique-coclique bound for Cayley graphs on abelian groups, and: K is a 16-clique of Cay(H, (K-K){0) while any tiling complement of K is an independent set of it
fp-11candidate2026-09-03
No 17-point subset of H = Z₄⁴ x Z₂ has all of its pairwise differences inside K - K
fp-12candidate2026-09-03
The clique number of Cay(H, (K-K){0) is exactly 16, attained by K – so the clique-coclique bound gives alpha <= 32, exactly the size of a tiling complement, and no clique certificate can replace the exact-cover search of Proposition 5.1(3)
fp-13candidate2026-09-03
Gamma carries 48 characters that are pairwise orthogonal on it, where spectrality would need 64: an explicit 48-point family, so the failure of spectrality is not degenerate
fp-14routine2026-09-03
Controls: a subgroup of the same size as Gamma is both a tile and spectral; K x 0 has the right cardinality to be a tiling complement of Gamma and is not one; a 3-point set is not a tile
fp-15measurement2026-09-03
MEASUREMENT: 48 is exactly the largest number of characters pairwise orthogonal on Gamma, and 16 is exactly the largest set whose pairwise differences are all Fourier NON-zeros of Gamma – so the clique-coclique bound is tight for Gamma too
This ledger entry is reported in prose and is not bound to a Lean theorem.fp-16known data2026-09-03
The source's Appendix B data for the binary example, transcribed mechanically: F₂¹3 is elementary abelian of order 8192 (x + x = 0), |R₂| = 512, |A₂ x 0| = 16, |Cⱼ| = 16 for all 17 j, and the standard dot product is nondegenerate
fp-17known2026-09-03
The source's Lemma 4.1, tiling half, for arbitrary finite abelian X and Y: if A + C_y = X for every y then (A x 0) + union_y (C_y x y) = X x Y; plus IsTiling is symmetric and splits over products
fp-18known data2026-09-03
The source's Proposition 4.2(1): A₂ + Cⱼ = H₂ = F₂⁸ for each of the seventeen complements
fp-19known data2026-09-03
The source's Proposition 4.2(2) and its printed 'common_fourier_zeros=108': |D₂| = 108, D₂ = intersection of the Z(Cⱼ), and W₂(v) = 0 iff v in D₂ for every nonzero v; plus its equation eq:horizontal-fourier, 1hat_(R₂)(v,0) = W₂(v)
fp-20known data2026-09-03
The source's Proposition 4.2(4) and its printed 'weightedₙoncancellation=1 minimumₐbs_weighted_fourier=4': the minimum of |W₂(v)| over v outside D₂ u 0 is exactly 4
fp-21known data2026-09-03
The source's Proposition 4.2(3) and its 'common_zero_cliqueₙumber=12 no₁6_clique=1': the clique number of Cay(F₂⁸, D₂) is exactly 12, by an exhaustive search with NO colouring prune whose completeness is proved in the kernel
fp-22known data2026-09-03
The source's Theorem 1.2(2): the 512-point R₂ tiles F₂¹3 with complement A₂ x 0 and is not spectral – so Malikiosis' Conjecture 1.3 fails already in an ELEMENTARY ABELIAN 2-group
fp-23routine2026-09-03
The fibre-clique lemma quantified: for arbitrary finite abelian X and Y, every family of characters pairwise orthogonal on R = union_y (C_y x y) has at most |Y| * omega(Cay(X,D)) elements; the source's non-spectrality is the special case |Y| * omega < |R|
fp-24candidate2026-09-03
R₂ admits EXACTLY 384 characters of F₂¹3 pairwise orthogonal on it, where spectrality needs 512 – the same 3/4 ratio as Gamma's 48 of 64
fp-25candidate2026-09-03
A SMALLER elementary abelian counterexample: a 128-point translational tile of F₂¹1 (order 2048) with tiling complement A₂ x 0 of size 16 and no spectrum, carrying exactly 96 pairwise orthogonal characters of the 128 that spectrality needs
fp-26candidate2026-09-03
D₂ is intrinsic to the base tile: D₂ = v!= 0: 1hat_(A₂)(v)!= 0; and since 1hat_A * 1hat_C vanishes off the origin for every tiling A + C = F₂⁸, the clique number is at least 12 for EVERY choice of tiling complements of A₂ in EVERY layer group – the source's certificate is optimal for its base, with slack exactly 4 against q = 16
fp-27routine2026-09-03
Controls for the binary example: a subgroup of F₂¹3 of R₂'s size that is both a tile and spectral; a 16-point set with the right cardinality that is not a tiling complement of R₂; 3-point non-tiles in F₂¹3 and F₂¹1; the Fourier test is not vacuous on either tile; the clique search returns true at target 11 on both difference sets
fp-28measurement2026-09-03
MEASUREMENT: the layer search is complete at k <= 3 over the seventeen printed complements – all 17 + 153 + 4845 multisets at k = 0,1,2 give a 16-clique, and exactly 3 of the 735,471 at k = 3 do not; and every one of the 193,536 tiling complements of A₂ in F₂⁸ is spectral
This ledger entry is reported in prose and is not bound to a Lean theorem.Provenance
- Generated by
- Machina Mathematica
- Released by
- Korea Superintelligence Labs
- Source context
- Let G be a finite abelian group and Ĝ its character group.
- Snapshot
- 2026-09-07 03:53 UTC
- Ledger commit
801848d7