Which designs tile

Which designs tile

Fix a base b >= 2 and a digit set F inside {0..b-1} with k = |F| >= 2. The level n of the dimension-one design is the finite set A_n = {sum_{i<n} d_i b^i : d_i in F} of k^n integers, and its mask is A_n(x) = prod_{i<n} F(x^(b^i)) with F(x) = sum_{d in F} x^d. A finite set A tiles the integers when A + C = Z with every integer written once; it is spectral when some set of |A| frequencies theta has A(e(theta - theta')) = 0 for every two of them, e(t) = exp(2 pi i t). Every verdict on this page is read from one object, the zero set of the digit transform hat F(t) = sum_{f in F} e(f t) at roots of unity, and every number is printed by lab/py/level-tiles or, for the limit measure, lab/py/measure-spectra.

The object

  • Z(F) = {m >= 2 : Phi_m | F(x)}, the orders of the roots of unity where hat F vanishes; hat F(a/m) = 0 with gcd(a, m) = 1 exactly when m is in Z(F).
  • Z_p(F) = {a >= 1 : p^a in Z(F)} for a prime p, and e_p = v_p(b), the exponent of p in the base.
  • S_A is the set of prime powers s with Phi_s | A(x). Coven and Meyerowitz read two conditions on it: T1 A(1) = prod_{s in S_A} Phi_s(1), and T2 Phi_{s_1 ... s_m} | A(x) whenever s_1, ..., s_m in S_A are powers of distinct primes.
  • Their theorems, read at source: T1 and T2 imply that A tiles (Theorem A); a tile satisfies T1 (Theorem B1); a tile whose size has at most two prime factors satisfies T2 (Theorem B2). Whether every tile satisfies T2 is open.
  • The tiling depth of F at base b is the largest n such that A_1, ..., A_n all tile, inf when every level tiles.

The index lemma

Proved. Phi_m | A_n(x) if and only if m/gcd(m, b^i) is in Z(F) for some i < n, and the multiplicity of Phi_m in A_n is sum_{i<n} of the multiplicity of Phi_{m/gcd(m, b^i)} in F. A primitive m-th root zeta makes zeta^(b^i) a primitive root of order m/gcd(m, b^i), so F(zeta^(b^i)) = 0 exactly when that order is in Z(F); and Phi_u(x^K) is a product of distinct cyclotomic polynomials, so multiplicities add over the factors F(x^(b^i)). In Fourier terms the zero set of hat F_n(t) = prod_{i<n} hat F(b^i t) on Q/Z is the union over i < n of the preimages of the zero set of hat F under t -> b^i t; one step of it is Coven-Meyerowitz Lemma 1.1(7).

For a prime power the lemma reads off the level exponents: p^a is in S_{A_n} exactly when a is in Z_p(F) for p not dividing b, and when a - e_p i is in Z_p(F) for some i < n for p | b. Every census verdict below is computed from Z(F) through this lemma and never from a factorisation of the level. (Verified: PARI factors 752 masks, every digit set with 0 at bases 2 to 8, levels 1 to 3 and level 4 at bases up to 4, and the cyclotomic part equals the lemma with multiplicity on all 752; index.)

The hand check

The Cantor level {0, 2, 6, 8}, level 2 of {0, 2} at base 3, has mask (1 + x^2)(1 + x^6) = Phi_4^2 Phi_12, so S = {4} and T1 reads |A_2| = 4 against Phi_4(1) = 2: it does not tile. (Verified: PARI and the lemma agree on Phi_4^2 Phi_12, and no complement exists in Z/N for 4 | N <= 128; hand.)

The tiling levels form an initial segment

Proved. If A_n tiles then A_m tiles for every m <= n. Digits below the base give unique expansions, so A_n = A_m + b^m A_(n-m) with every element written once, and A_n + C = Z gives A_m + (b^m A_(n-m) + C) = Z. So the tiling levels are 1..N for the depth N, and a digit set that does not tile Z has no tiling level at all: no non-tiling F has a tiling level.

A digit set that tiles its residues tiles every level

Proved. If F + E = Z/b with every residue written once, then A_n + E_n = Z/b^n with E_n = sum_{i<n} b^i E, so every level tiles the integers with period b^n. The set D = F + E is a complete residue system mod b, and D_n = sum_{i<n} b^i D is one mod b^n: a residue r fixes d_0 in D by r mod b, then (r - d_0)/b fixes d_1, and so on, the carry automaton of cuts run on the digit polynomial D(x) = F(x) E(x), which is 1 + x + ... + x^(b-1) mod x^b - 1. Each d_i splits uniquely as f_i + e_i, so the sum A_n + E_n is direct.

The converse is the guess, and it is false (below). What survives is a condition on Z(F) alone.

T1 at every level

Proved. T1 holds at every level A_n if and only if

  • T1 holds for F, that is k = prod_p p^|Z_p(F)|;
  • Z_p(F) is empty for every prime p not dividing b;
  • for every p | b the elements of Z_p(F) are pairwise incongruent mod e_p.

By the index lemma the exponents of p in S_{A_n} are Z_p(F) when p does not divide b and the union of the translates Z_p(F) + e_p i, i < n, when it does. T1 at level n compares v_p(k^n) = n v_p(k) with the size of that set. Off the base the size is constant, so v_p(k) = |Z_p(F)| = 0. On the base the union has at most n |Z_p(F)| elements and level 1 gives v_p(k) = |Z_p(F)|, so T1 holds for every n exactly when the translates are pairwise disjoint, that is when no two elements of Z_p(F) differ by a positive multiple of e_p.

Corollaries, Proved.

  • If every level tiles then |F| divides b: T1 is necessary (Theorem B1), and the condition forces |Z_p(F)| <= e_p.
  • The T1 depth, the largest n with T1 at levels 1..n, is 0 when F fails T1, 1 when some prime off the base has Z_p(F) nonempty, and otherwise the least (c' - c)/e_p over pairs c < c' in some Z_p(F) with c = c' mod e_p, inf when there is none.
  • When |F| is a prime power, T2 is vacuous at every level, so the tiling depth equals the T1 depth and every level tiles exactly when the three conditions hold.
  • When the base is a prime power p^e, every level tiles exactly when F tiles Z/b. A factor Phi_{p^a} with a > e has degree p^(a-1)(p-1) >= p^e > deg F, so Z_p(F) lies in 1..e, the size of F is a power of p, and the Coven-Meyerowitz complement of F has period lcm(S_F), a divisor of b.

The depth can stop anywhere. {0, 1, 4, 5} at base 6 has mask Phi_2 Phi_8, Z_2 = {1, 3} and e_2 = 1, so levels 1 and 2 tile and level 3 does not; {0, 1, 8, 9} at base 10 has Z_2 = {1, 4} and stops at level 3. (Verified: on all 65519 digit sets with 0 at bases 2 to 16 the census asserts the T1 depth formula against the T1 depth read level by level to level 16, the tiling depth against the least of the T1 depth, the T2 depth and 8, which equals the T1 depth at every prime-power size while T2 cuts below it on 771 sets of the other sizes, and the prime-power-base law, and prints depth 2 at bases 6, 10 and 14 and depth 3 at bases 10 and 14; census, witness.)

The guess is false

The guess: every level tiles exactly when F tiles Z/b. One direction is the residue section above; the other fails.

Refuted, twice.

  • F = {0, 2} at base 6. {0, 2} does not tile Z/6, since translation by 2 has odd cycles on Z/6, yet Z(F) = {4}, Z_2 = {2}, e_2 = 1, and every level tiles by the T1 condition. The cure is to divide by the gcd: tiling is invariant under scaling (Coven-Meyerowitz Lemma 1.4), and {0, 1} tiles Z/6.
  • F = {0, 1, 8, 9} at base 12, with gcd 1. Its mask is (1 + x)(1 + x^8) = Phi_2 Phi_16, so Z_2 = {1, 4}, e_2 = 2, and 1, 4 are incongruent mod 2: T1 holds at every level, and |A_n| = 4^n is a prime power, so every level tiles. F itself tiles Z with period 16, {0, 1, 8, 9} + {0, 2, 4, 6} = {0..15}. But it does not tile Z/12: a complement E of size 3 would carry Phi_3, Phi_4, Phi_6 and Phi_12, since F vanishes at none of those orders, and T1 for E would read 3 against at least Phi_3(1) Phi_4(1) = 6. No integer multiple vF tiles Z/12 either. Scaling raises both exponents, Z_2(vF) = {1 + v_2(v), 4 + v_2(v)} by Coven-Meyerowitz Lemma 1.4(2), and their Lemma 2.1 puts every element of S_vF among the prime powers dividing 12 when vF tiles Z/12; whatever happens to 1 + v_2(v), the power 2^(4 + v_2(v)) never divides 12. (Verified: an exact-cover search over v = 1..12, every class mod 12, finds no complement for vF or for v{0, 3, 8, 11}; witness.)

Verified. No base below 12 has a counterexample after the gcd: over the 65519 digit sets at bases 2 to 16, 609 tile at every level and 588 tile Z/b; of the 21 that tile at every level without tiling Z/b, 19 are cured by the gcd, and the remaining two are {0, 1, 8, 9} and {0, 3, 8, 11} at base 12, both mirror-symmetric, zero sets {2, 16} and {2, 6, 16} (census). The levels of {0, 1, 8, 9} at base 12 tile with complements {0, 2, 4, 6} mod 16, {0, 2, 16, 18} mod 64 and {0, 2, 64, 66} mod 256 (witness). The reason is visible in the T1 condition: a counterexample after the gcd needs an exponent c in some Z_p(F) above e_p, which the degree bound forbids at a prime-power base; a prime size p is cured by the gcd, since Phi_{p^c} | F with |F| = p puts F in one class mod p^(c-1); size 4 needs 4 | b, and 12 is the first base divisible by 4 that is not a prime power.

T2 at every level

Proved. If F satisfies T1 and T2 and lcm(S_F) divides b, then every level satisfies T1 and T2, so every level tiles; this is the case where F tiles Z/b through its Coven-Meyerowitz complement. Each exponent c in Z_p(F) is at most e_p, so they are incongruent mod e_p. A T2 instance at level n takes, for distinct primes p_j, exponents c_j + e_j i_j with c_j in Z_{p_j}(F) and i_j < n; at l = max i_j the index lemma reduces it to prod p_j^((c_j - e_j(l - i_j))_+), which keeps only the primes with i_j = l and their exponents c_j, a product of elements of S_F at distinct primes, and T2 for F puts it in Z(F).

Proved (the horizon). Assume the T1 condition. Let C_p be the largest exponent of p in an element of Z(F), G the largest ceil(C_p/e_p) over the omega primes with Z_p(F) nonempty. Then T2 holds at every level if and only if it holds at levels 1..1 + G(2 omega - 1). A T2 instance is hardest at the level 1 + max i_j, and its witnesses are the l <= max i_j whose reduction lies in Z(F). Every witness has l >= i_j - G for every j, since otherwise the exponent of p_j exceeds C_{p_j}. So an instance with min i_j > G can be lowered to min i_j = G with its witnesses; and if the sorted i_j have a gap above 2G, every witness lies more than G above each lower i_j, the lower primes vanish at every witness, and the instance stands or falls with its upper part. The reduced instances have max i_j <= G + 2G(omega - 1). (Verified: on the census the horizon agrees with T2 checked six levels past it on every digit set that passes the T1 condition; census.)

Proved. F = {0, 1, 2, 6, 7, 8} at base 18 tiles the integers and satisfies T1 at every level, yet level 2 does not tile. The mask of F = {0, 1, 2} + {0, 6} is Phi_3 Phi_4 Phi_12, so S_F = {3, 4}, T1 and T2 hold, and F tiles with period 12; Z_2 = {2}, Z_3 = {1} satisfy the T1 condition with e_2 = 1, e_3 = 2. At level 2 the exponents are {2, 3} for 2 and {1, 3} for 3, so T2 asks for Phi_108 = Phi_{4 * 27}; the index lemma gives 108/gcd(108, 1) = 108 and 108/gcd(108, 18) = 6, neither in Z(F) = {3, 4, 12}. |A_2| = 36 has two prime factors, so Theorem B2 says A_2 does not tile. So F tiles Z, T1 holds at every level, and level 2 still fails, through T2.

Verified. No base below 18 has such a digit set. Over the digit sets of a size with two prime factors below the base, at bases up to 30 with at most 200000 sets a cell, those that tile, pass the T1 condition, and fail T2 at a level up to 6 number 0 of size 6 at base 12, 16 of size 6 (10 up to mirror) at base 18, 0 of size 10 at base 20, 4 of size 6 at base 24 and 258 of size 6 (141 up to mirror) at base 30, every one failing at level 2; size 12 at base 24 (1352078 sets), size 14 at base 28 (20058300) and sizes 10 and 15 at base 30 exceed the cap and are skipped; at bases below 18 the only such size is 6 at base 12 (witness). A level-2 failure of this kind needs an exponent above e_p together with T2 for F, and the degree of Phi_{p^c} Phi_{q^d} Phi_{p^c q^d} must fit below b.

The classification

Proved. For a base b and a digit set F in {0..b-1}:

  • every level tiles only if F passes the T1 condition, and then |F| divides b;
  • if |F| is a prime power, every level tiles if and only if F passes the T1 condition;
  • if |F| has two prime factors, every level tiles if and only if F passes the T1 condition and T2 holds at levels 1..1 + G(2 omega - 1);
  • if |F| has three or more prime factors, the same condition is sufficient, and its necessity is the open necessity of T2; such a size divides b, is below it, and so needs b >= 60;
  • if b is a prime power, every level tiles if and only if F tiles Z/b.

The first two lines and the prime-power base are T1 alone; the third is Theorems A, B1 and B2 applied level by level through the index lemma and the horizon.

Spectral levels

Proved. If T1 and T2 hold at every level, every level is spectral, by Łaba's Theorem 1.5(i) applied to each A_n; with the classification, every level is spectral whenever every level tiles and |F| has at most two prime factors. The spectrum is explicit: sums of j/s over s in S_{A_n}, 0 <= j < p for s a power of p, as in Łaba-Wang's proof of their Theorem 1.4.

Verified. On the 6866 levels with |A_n| <= 36 at bases 2 to 12 and levels 1 to 3, a level is spectral exactly when it tiles, on all 6749 levels the search decides. The search is complete for rational spectra: a spectrum through 0 has every element theta with A_n(e(theta)) = 0, so a rational one lies in (1/L)Z for L = lcm Z(A_n), and a clique search on Z/L with the edges L/gcd(d, L) in Z(A_n) finds one or proves none. It is complete for all spectra when every root of F on the unit circle is a root of unity, since a root of A_n on the circle is then one too; PARI finds the other kind of root on 77 of the 4083 digit sets, and their 117 non-tiling levels with no rational spectrum stay undecided. The spectra found are re-checked numerically (spectral).

Conjecture. A level of a dimension-one design is spectral if and only if it tiles. This is Fuglede's conjecture on a structured family of integer sets; its tiling side is the classification above.

The limit measure

The limit of the levels is the self-similar measure mu_{b,F}, the weak limit of the uniform measure on b^(-n) A_n. The guess for it: mu_{b,F} is spectral exactly when every level of F at base b tiles. Łaba and Wang conjectured the stronger form, that a spectral mu has F a rational multiple of a complementing set mod b (their Conjecture 3.1(c)); at base 12 {0, 1, 8, 9} is no such multiple, while its measure is spectral (the level shift, below) and meets the condition of Liu-Wang-Zheng Theorem 1.3, an unrefereed arXiv preprint, so the residue form fails for the measure of this witness too. An-Lai Example 1.3 and An-He-Lai Section 1.1 quote from Dutkay and Jorgensen the measure of {0, 1, 8, 9} at base 4, a spectral measure whose digits are not distinct mod the base.

Proved. For consecutive digits F = {0..N-1}, every level tiles if and only if N | b: Z(F) is the divisors of N above 1, Z_p(F) = {1..v_p(N)}, the T1 condition reads v_p(N) <= e_p, and then lcm(S_F) = N divides b, so T2 holds at every level. Dai, He and Lau prove that mu_{b,{0..N-1}} is spectral if and only if N | b, so the guess holds on this family. For {0, 2} the T1 condition needs b even, and Jorgensen and Pedersen prove that at odd base R at most two exponentials are orthogonal in L^2(mu), the base-3 Cantor measure among them, while base 4 is spectral. (Verified: N | b against the every-level verdict on all 2016 pairs 2 <= N <= b <= 64; measure.)

Verified. For the product-form digit sets {0..N-1} + m{0..L-1}, T1 and T2 at every level agree with the spectral condition of Liu-Wang-Zheng Theorem 1.3, stated in an unrefereed arXiv preprint, N | p, L | p and N | m/gcd(m, p^d) with d the largest i >= 0 such that mL/gcd(mL, p^i) shares a factor with L, on all 576422 cases with base p <= 24, 2 <= N, L <= 12 and N <= m <= p^2; no case passes the T1 condition and fails T2 with three primes, so on the box the every-level verdict is a tiling verdict (measure). Here digits exceed the base and a level can be a multiset; T1 and T2 force a set, since the Coven-Meyerowitz complement B of the proof of Theorem A gives A_n(x) B(x) = 1 + x + ... + x^(M-1) mod x^M - 1, M = |A_n| |B|, with non-negative coefficients (their Lemma 1.3), so every coefficient of A_n(x) is 0 or 1. The zero set of a product-form mask comes from the index lemma for one power, Z({0..N-1}) + Z({0..L-1}(x^m)). A comparison that read only levels up to 8 would disagree on {0, 1} + 256{0, 1} at base 18, whose T1 depth is exactly 8: the T1 condition is what reads every level.

Conjecture. For an integer base b >= 2 and a finite digit set F in the non-negative integers containing 0, the measure mu_{b,F} is spectral if and only if every level A_n is a set that tiles the integers. The direction from spectral to tiling levels is a question of An and coauthors, quoted by Wu and Xiao, an arXiv preprint, which settles it for equidifferent digit sets of prime size and shows the converse fails for Cantor-Moran measures with varying digit sets; the other direction, from tiling levels to a spectrum, holds at prime-power size, at pq digits, at four digits or fewer and on every design of the census, below; the direction from a spectrum to tiling levels holds at four digits or fewer by An-He-Lai and at five digits with 0 in F and levels that are sets, below.

The measure in the Hadamard window

Write Lambda(b, L) = {sum_{j<n} b^j l_j : n >= 1, l_j in L} for a finite set L of integers containing 0. Łaba and Wang prove that when (b^(-1) F, L) is a compatible pair, that is hat F((l - l')/b) = 0 for distinct l, l' in L and |L| = |F|, the measure mu_{b,F} is spectral, and that Lambda(b, L) is a spectrum when moreover gcd(F - F) = 1, 0 is in L and L lies in [2 - b, b - 2]; for b >= 3 a choice of representatives mod b arranges the last condition, and either representative of a residue works (their Theorem 1.2 and Lemma 2.2(b), (d)). At b = 2 the interval is {0}, and the only digit sets are {0, 1} up to scaling, whose measure is Lebesgue measure on [0, 1] with spectrum Z.

Proved. If b >= 3, 0 is in F, F' = F/gcd(F) satisfies T1 and T2 and lcm(S_{F'}) divides b, then mu_{b,F} is spectral with spectrum gcd(F)^(-1) Lambda(b, L), where L is {sum_{s in S_{F'}} k_s b/s : 0 <= k_s < p_s}, p_s the prime of s, with each element replaced by a representative mod b in [2 - b, b - 2]. Since 0 is in F', gcd(F' - F') = gcd(F') = 1. Each b/s is an integer since s | b. For distinct l, l' the number (l - l')/b is sum (k_s - k'_s)/s, and grouping by primes it is r/m with gcd(r, m) = 1 and m the product, over the primes where some k_s differs, of the largest such s; T1 and T2 put Phi_m in the mask of F', so the pair is compatible, and mu_{b,F} is the image of mu_{b,F'} under x -> gcd(F) x. This is the proof of Łaba-Wang Theorem 1.4 with T2 assumed in place of the two-prime count, and by the T2 section above it is the case where F' tiles Z/b through its Coven-Meyerowitz complement. (Verified: 607 of the 609 every-level designs at bases 2 to 16 carry a Hadamard triple (b, F', L) with L in Z, found by a clique search on Z/b; census of lab/py/measure-spectra.)

Iterating does not widen the window: the spectrum above for the level A_n at base b^n needs every exponent of p in S_{A_n} at most n e_p, and the top one is max Z_p(F) + e_p(n - 1). The two designs without one at bases up to 16 are {0, 1, 8, 9} and {0, 3, 8, 11} at base 12.

Proved. No level of {0, 1, 8, 9} at base 12 has a spectrum inside 12^(-n) Z, so no integer Hadamard triple (12^n, A_n, L) exists at any level. By the index lemma an order m dividing 12^n lies in Z(A_n) exactly when m/gcd(m, 12^i) is 2 or 16 for some i < n, so every such order is even and its exponent of 2 lies in {1, 3, ..., 2n - 1} ∪ {4, 6, ..., 2n}, a set of 2n - 1 values. A spectrum Gamma in Z/12^n then maps injectively to Z/2^(2n), since two points with one image differ by an element of odd order, and the 2-adic valuations of its differences take 2n - 1 values; a set whose binary tree branches at 2n - 1 levels has at most 2^(2n - 1) < 4^n points.

The level shift

Proved. Let mu = nu * rho, where nu is the uniform measure on a finite set S with a spectrum Lambda_0 of |S| points, rho has a spectrum Gamma containing 0, and gamma (s - s') is an integer for every gamma in Gamma - Gamma and s, s' in S. Then Lambda_0 + Gamma is a spectrum of mu. Write hat mu(xi) = ∫ e(xi x) dmu(x) for the Fourier transform of a measure, and likewise hat nu, hat rho. The condition makes |hat nu| invariant under Gamma - Gamma, so two points with different Lambda_0 parts are orthogonal through hat nu and two with the same part through hat rho; and Q(xi) = sum_lambda |hat mu(xi + lambda)|^2, Bessel's sum for e(xi x) against the family, is sum_{lambda_0} |hat nu(xi + lambda_0)|^2 sum_gamma |hat rho(xi + lambda_0 + gamma)|^2 = sum_{lambda_0} |hat nu(xi + lambda_0)|^2 = 1, so every exponential lies in the closed span, which is all of L^2(mu).

For a direct sum F = G ⊕ H and q >= 1, rearranging the infinite convolution gives mu_{b,F} = nu * mu_{b, G + b^(-q) H} with nu uniform on S = sum_{j=1..q} b^(-j) H: the factors b^(-j) H with j <= q stay in nu, the rest move up q levels. This is the decomposition in the proof of Liu-Wang-Zheng Theorem 3.5, here for any direct sum.

Proved. mu_{12,{0,1,8,9}} is spectral with spectrum {0, 3/4} + 3 Lambda(12, {0, 3, 6, 9}). Take G = {0, 1}, H = {0, 8}, q = 1: S = {0, 2/3} has spectrum {0, 3/4}, and G + H/12 = (1/3){0, 2, 3, 5}. The mask of {0, 2, 3, 5} = {0, 3} ⊕ {0, 2} is Phi_2 Phi_4 Phi_6, so (12^(-1){0, 2, 3, 5}, {0, 3, 6, 9}) is compatible, and Łaba-Wang Theorem 1.2 makes Lambda(12, {0, 3, 6, 9}) a spectrum of mu_{12,{0,2,3,5}}; scaling by 1/3 makes 3 Lambda(12, {0, 3, 6, 9}) a spectrum of the second factor, and it lies in 3Z, where gamma * 2/3 is an integer. The same steps give {0, 5/6, 5/3} + 5 Lambda(30, {0, 5, 10, 15, 20, 25}) for {0, 1} ⊕ 12{0, 1, 2} at base 30, a design of pq digits outside the Hadamard window, its exponent of 3 being 2 > e_3 = 1. (Verified: both spectra are orthogonal in exact arithmetic, and 1 - min Q over 32 points of [-1, 1] falls to 1.73e-05 at depth 6 and 9.30e-07 at depth 5; the controls Lambda(4, {0, 3}) for {0, 2} at base 4, which keeps Q(1) = 0 through the cycle at 1 of Łaba-Wang Theorem 1.3, and Lambda(12, {0, 3, 6, 9}) alone for {0, 1, 8, 9}, which is not orthogonal, fail; spectra.)

The measure at prime-power size

Proved (the tree lemma). Let |A| = p^r with T1, so that S_A is {p^(c_1), ..., p^(c_r)}, c_1 < ... < c_r. Then each class of A mod p^(j-1) meets all p classes mod p^j above it, equally, when j is some c_i, and exactly one of them otherwise. Phi_(p^j) divides A(x) exactly when the p classes mod p^j inside each class mod p^(j-1) hold equally many elements of A, since a polynomial reduced mod x^(p^j) - 1 is a multiple of Phi_(p^j)(x) = sum_{s<p} x^(s p^(j-1)) exactly when its coefficients are constant on each coset of p^(j-1) Z / p^j Z. Follow one element: the count of its class starts at p^r, is divided by exactly p at each c_i, never grows, and is 1 far out; the r divisions already bring p^r to 1, so no other level splits a class.

Proved. If |F| = p^r and every level of F at base b tiles, then mu_{b,F} is spectral. By the T1 section e = e_p >= 1 and the c_i are pairwise incongruent mod e; write rho_i for the residue of c_i in 1..e and b = p^e b'. Cut each digit into base-p^e windows, f = sum_j r_j(f) p^(ej), so that b'^K f = sum_{j <= K} b^j b'^(K-j) r_j(f) for K the last window. For a class d mod p^(ej) met by F, let R_j(d) be the set of the distinct values r_j(f) over the f in that class, which are the classes mod p^(e(j+1)) that F meets inside d; by the tree lemma the number of those classes below a class mod p^l met by F, ej <= l <= e(j+1), is p to the number of c_i in (l, e(j+1)], the same for every class, so R_j(d) splits equally, p ways, exactly at the levels c_i - je in 1..e, and Phi_(p^(rho_i)) divides its mask for those i, and so the mask of E_j(d) = b'^(K-j) R_j(d), the factor being prime to p. With L_j = {sum k_i b/p^(rho_i)} over the window's i, every (b, E_j(d), L_j) is a Hadamard triple by the argument of the Hadamard window, and since the rho_i of all windows are distinct, so is every sum E_m(d_m) ⊕ ... ⊕ E_(m')(d_(m')) with L_m ⊕ ... ⊕ L_(m'); the sizes match, and a Hadamard matrix has rank equal to its size, so each sum is direct. An-Lai Definition 2.3, read at source, asks for each single window and, for every 1 <= m <= k, for the prefix E_0 ⊕ ... ⊕ E_m with L_0 ⊕ ... ⊕ L_m and the suffix E_m ⊕ ... ⊕ E_k with L_m ⊕ ... ⊕ L_k; the argument here gives every range of consecutive windows, which contains those. So this is a K-stage product-form Hadamard triple in their sense, with N = b and every l_j = 1, their Theorem 2.4 makes mu_{b, b'^K F} spectral, and mu_{b,F} is its image under x -> x/b'^K.

The base-12 witness is the case r = 2. The set {0, 1, 8, 25} = ({0} + 4{0, 2}) ∪ ({1} + 4{0, 6}) of An-Lai Example 1.6 is no direct sum, and at base 28 it tiles at every level, so its measure is spectral by this theorem and by none of the sections above; the candidate spectrum {0, 7/4} + 7 Lambda(28, {0, 7, 14, 21}), read off its exponents {1, 4} as for the base-12 witness, is orthogonal and gives 1 - min Q = 5.38e-04 at depth 6 (spectra), and whether a spectrum read from the exponents alone is complete for every tree set is not decided here. (Verified: every gcd-1 tree set of size 2^r with an exponent above e_2 at bases 12, 20, 24, 28, 36, 40, 44, 48, and of size 9 with an exponent above e_3 at bases 36, 45, 72, tiles at every level and passes conditions (i) and (ii) of Definition 2.3 in exact arithmetic, 314 of 314, as do the 40 census designs of prime-power size without a Hadamard triple; hunt and census of lab/py/measure-spectra.)

The measure at four digits or fewer

An-He-Lai classify the spectral self-similar measures with at most four maps, read at source: for four integer digits their Theorem 4.2 with the sufficiency of their Section 4.1 is an if and only if, mu_{b,F} spectral exactly when b = 2^beta m with beta >= 1 and m odd and F is, up to scaling, {0, a, 2^t l, a + 2^t l'} with a, l, l' odd and beta not dividing t (their Theorem 1.7 states the necessity); for two and three digits their Theorem 5.1 gives the necessity, b even for {0, a}, and 3 | b with F a rational multiple of a complete residue system mod 3 for three digits, and a compatible pair gives the sufficiency. What this page proves is that their condition is the every-level verdict.

Proved. If |F| <= 4, the condition of An-He-Lai Theorems 4.2 and 5.1, read at source, holds exactly when every level of F at base b tiles, so by their classification mu_{b,F} is spectral if and only if every level tiles.

  • |F| = 2, F = {0, a}: every level tiles exactly when b is even, by the T1 condition with Z_2(F) = {v_2(a) + 1}.
  • |F| = 3: a set of size 3 divisible by Phi_(3^c) is 3^(c-1) C with C a complete residue system mod 3, so every level tiles exactly when F has this form and 3 | b.
  • |F| = 4: by the tree lemma at p = 2, T1 for F says that F/2^v, v = v_2(gcd F), has two even and two odd elements, the evens differing by 2^t times an odd number and the odds by 2^t times an odd number for one t >= 1, the exponents being v + 1 and v + 1 + t; the T1 condition then reads that b is even and t is not a multiple of beta = v_2(b).

(Verified: every four-digit set {0, a_1, a_2, a_3} in {0..b-1} at bases 4 to 36, 58905 sets of which 2642 tile at every level, has the every-level verdict equal to the An-He-Lai condition; four.) So the guess for the limit measure holds at every size up to 4, in both directions.

The measure at pq digits

Proved (the fibre lemma). Let N = p^alpha q^beta with alpha, beta >= 1. If Phi_N divides a polynomial P with non-negative integer coefficients, then the exponents of P mod N, with multiplicity, are a union of p-fibres {x + kN/p : k < p} and q-fibres {x + kN/q : k < q}. Put zeta = e(1/N) and omega = zeta^(N/pq), of order pq; the minimal polynomial of zeta over Q(omega) is x^(N/pq) - omega, both degrees being N/pq, so P(zeta) = sum_{r < N/pq} zeta^r G_r(omega) vanishes exactly when every G_r(omega) does, G_r holding the counts g on the coset r + (N/pq)Z, a copy of Z/p x Z/q. There G_r(omega) = 0 says that the transform of g vanishes off the two axes, so g(i, j) = g(0, j) + (g(i, 0) - g(0, 0)): a column term, counting p-fibres, plus a row term, counting q-fibres; subtracting the least row term, taken at a row i*, from every row and adding it to every column makes both non-negative: the new row terms are at least 0, and the new column term is g(i*, j) >= 0, which is where the non-negativity of P enters. The statement is classical: it is Lam-Leung Theorem 3.3(2) with the reduction of their Theorem 3.1 to the subgroup of order pq, which they trace to de Bruijn, read at source; the proof given is self-contained.

Proved (the shape at pq digits). Let |F| = pq with p != q primes, 0 in F, gcd(F) = 1, and every level of F at base b tiling. Then, naming the primes suitably, Z_q(F) = {1}, Z_p(F) = {c}, and F = ⋃_{j<q} (x_j + p^(c-1) q K_j) with the x_j distinct mod q and each K_j a complete residue system mod p. By the T1 section and Theorem B2, Phi_(p^c), Phi_(q^d) and Phi_(p^c q^d) divide F, and the fibre lemma at N = p^c q^d writes F mod N with pq = p A + q B fibres' worth of points, so, since p divides B, F is q p-fibres or p q-fibres. A q-fibre x + p^c q^(d-1){0..q-1} is one point mod p^c, so in the second case F mod p^c meets at most p residues, which the p fibres may share; by the tree lemma every class mod p^(c-1) met by F meets all p classes mod p^c above it, so counting classes puts F in one class mod p^(c-1), which holds 0: p^(c-1) divides gcd(F) and c = 1. Symmetrically the first case forces d = 1. In either case one prime has exponent 1 and the fibres run along the other; call the first q, so that F is q p-fibres x_j + p^(c-1) q {0..p-1} mod p^c q, and write each element as x_j + p^(c-1) q k + p^c q t = x_j + p^(c-1) q (k + p t). Each group lies in one class mod q, and Phi_q asks for p elements in every class, so the x_j are distinct mod q.

Proved (three evaluations). For F of this shape:

  • for 1 <= alpha <= c - 1, Phi_(p^alpha q) divides F if and only if the x_j lie in one class mod p^alpha;
  • for beta >= 1, Phi_(p^c q^(1 + beta)) divides F if and only if every K_j lies in one class mod q^beta;
  • for 1 <= alpha <= c - 1 and beta >= 1, Phi_(p^alpha q^(1 + beta)) does not divide F.

Let zeta have the order in question and eta = zeta^(p^(c-1) q), so that F(zeta) = sum_j zeta^(x_j) K_j(eta). In the first case eta = 1, F(zeta) = p sum_j zeta^(x_j), and with zeta the product of a root of order p^alpha and one of order q, the q powers of the second are all q-th roots of unity, whose only linear relation over Q(e(1/p^alpha)) has equal coefficients: the sum vanishes exactly when the e(x_j/p^alpha) agree. In the second case eta has order p q^beta and the minimal polynomial of zeta over Q(eta) is x^(p^(c-1) q) - eta, so the zeta^(x_j), the x_j being distinct mod p^(c-1) q, are independent over Q(eta) and F(zeta) = 0 exactly when every K_j(eta) = 0, which by the argument of the first case with p and q exchanged says each K_j lies in one class mod q^beta. In the third case eta has order q^beta, the powers zeta^(x_j) carry q distinct roots of order q^(1+beta) up to factors in Q(e(1/p^alpha), eta), independent over that field, so F(zeta) = 0 would need some K_j(eta) = 0, that is Phi_(q^beta) dividing a set of p elements, and q does not divide p.

Proved. If |F| = pq with p != q primes and every level of F at base b tiles, then mu_{b,F} is spectral: with F' the translate of F through 0 divided by its gcd and the primes named so that Z_q(F') = {1} and Z_p(F') = {c}, either c <= e_p and the Hadamard window applies, or a e_p < c <= (a + 1) e_p and (b, (b/b_P)^a F', L_1 ⊕ L_2) is a product-form Hadamard triple of An-Lai Definition 2.1 with r = a, b_P = p^(e_p) q^(e_q), L_1 = (b/q){0..q-1} and L_2 = (b/p^(c - a e_p)){0..p-1}, whose direct sum L_1 ⊕ L_2 is the set of sums l_1 + l_2. Translating and dividing by the gcd keep the measure spectral or not and every level tiling, so it suffices to treat F = F', of the shape above; write e = e_p and f = e_q. If c <= e, then lcm(S_F) = p^c q divides b and the Hadamard window applies. If c > e, let a >= 1 with a e < c <= (a + 1) e. T2 at level a + 1 asks for Phi_(p^c q^(1 + f a)), the exponent c read at i = 0 and 1 + f a at i = a, and by the index lemma its witnesses are the l <= a with p^(c - e l) q^(1 + f(a - l)) in Z(F). At l = a the first evaluation puts the x_j, and with them all of F, in the class of 0 mod p^(c - e a), against gcd(F) = 1; the third rules out 0 < l < a; so l = 0, and by the second evaluation every K_j lies in one class mod q^(f a), K_j = kappa_j + q^(f a) K'_j with K'_j again complete mod p. With y_j = x_j + p^(c-1) q kappa_j and s = (b/b_P)^a,

s F = ⋃_j (s y_j + b^a B_j), B_j = p^(c-1-a e) q K'_j.

The set A = {s y_j} is complete mod q, so (b, A, L_1) is a Hadamard triple with L_1 = (b/q){0..q-1}; each B_j is divisible by Phi_(p^(c - a e)), so (b, B_j, L_2) is one with L_2 = (b/p^(c - a e)){0..p-1}, integers since c - a e <= e; and (b, A ⊕ B_j, L_1 ⊕ L_2) is one, since a difference with both parts nonzero has order p^(c - a e) q, where B_j(zeta) = K'_j(zeta^(q p^(c-1-a e))) is K'_j at a primitive p-th root, which is 0; L_1 ⊕ L_2 is direct mod b, and A ⊕ B_j is direct since A is distinct mod q and B_j is divisible by q. This is a product-form Hadamard triple of An-Lai Definition 2.1 with r = a, and their Theorem 2.2 makes mu_{b, sF} spectral, so mu_{b,F} is spectral. The base-30 family is the case a = 1: {0, 1} ⊕ 12{0, 1, 2} has p = 3, c = 2, groups x_j = 0, 1 and K_j = {0, 2, 4} in one class mod 2. An-Wang Theorem 1.7, as Liu-Wang-Zheng Section 1.1 quote it, classifies the spectral measures of strict product-form digit sets E_0 ⊕ b^l E_1, E_0 ⊕ E_1 = {0..pq-1}, with respect to pq; the original is not read here, so its overlap with this theorem is not determined.

(Verified: over every digit set of size 6 with 0 at bases 30, 36, 42 and 48, the every-level designs number 3221, 8867, 17360 and 37559, of which 14, 0, 55 and 0 have no Hadamard triple after the gcd, and each of these 69 has the shape, the class condition and the product-form triple in exact arithmetic; at base 66, over the digit sets with 0 below 36, 8087 designs tile at every level, 31 have no Hadamard triple after the gcd, and all 31 pass the same checks; pq of lab/py/measure-spectra.) The zeros at bases 36 and 48 are forced, as at 54: an outside design has each K_j in one class mod q^(f a), so its span is at least (p - 1) p^(c-1) q^(1 + f a) >= q b_P, which exceeds b - 1 when b = b_P; those bases test the window only.

The converse at prime size

The converse asks that a spectral mu_{b,F} have every level tiling. At source it is settled on few families: Łaba-Wang Theorem 1.4 is a sufficiency only, a complementing set mod b whose size has at most two prime factors giving a spectral measure, with the converse their Conjecture 3.1; Dai-He-Lau Theorem 1.1 settles consecutive digits {0..N-1}; An-He-Lai Theorem 5.1 settles two and three digits, so prime size p = 2, 3, and their closing remark leaves five or more digits open, naming {0, 1, 3, 5, 6}, whose transform vanishes only at irrational points. This section proves a necessary condition at every size, which zeros off the roots of unity cannot spoil, sharpens it to a covering bound, and with it proves the converse at five digits.

Write Theta for the finite set of zeros of hat F in [0, 1), so that the zero set of hat mu(xi) = prod_{j>=1} hat F(b^(-j) xi)/k is ⋃_{j>=1} b^j (Theta + Z); an integer d lies in it exactly when b^j/gcd(d, b^j) is in Z(F) for some j >= 1, and then d reaches that order at level j.

Proved (the class count). If A_n is a set of k^n integers, as when F lies in {0..b-1}, then a spectrum Lambda of mu = mu_{b,F} meets at least k^n classes of R/b^n Z. Write hat mu(xi) = hat mu_n(xi) hat mu(b^(-n) xi) with mu_n uniform on b^(-n) A_n; hat mu_n has period b^n and is 1 on b^n Z. Two points of one class Lambda_r differ by b^n z, so 0 = hat mu(b^n z) = hat mu(z), the set b^(-n) Lambda_r is orthogonal in L^2(mu), and Bessel's inequality bounds sum_{lambda in Lambda_r} |hat mu(b^(-n)(x - lambda))|^2 by 1. Splitting Parseval's sum_lambda |hat mu(x - lambda)|^2 = 1 by classes gives 1 <= sum_r |hat mu_n(x - r)|^2 for every x; with finitely many classes, the mean of |hat mu_n|^2 over a period is k^(-n), so their number is at least k^n.

Proved (finitely many rational cosets). A spectrum through 0 meets finitely many cosets of Q. In the Q-vector space R/Q its points and their differences map into {0} and the sets b^j x, j >= 1, with x the image of an irrational element of Theta. If infinitely many points mapped to b^j x for one x, with j in an infinite set K, then for j > j' in K the difference (b^j - b^(j')) x is some b^i c x with c x the image of an element of Theta, so b^(j - j') - 1 = c b^(i - j'). An integer prime to b equals c b^s for at most one s, and c takes finitely many values, so j - j' takes finitely many values on K, which is impossible.

Proved (integer orthogonal sets). If every A_n is a set and mu_{b,F} is spectral, then for every L >= 1 some k^L integers, pairwise incongruent mod b^L, have every difference a zero of hat mu. Take a spectrum Lambda through 0, its points Lambda_v in one coset of Q, and M the lcm of Z(F). Differences in Lambda_v are rational zeros, in M^(-1) Z, so Gamma = M(Lambda_v - lambda_v) is a set of integers whose classes mod M b^n are those of Lambda_v mod b^n Z. Two points c + M b^(tL) x and c + M b^(tL) x' of Gamma differ by M b^j (theta + i) with theta a rational zero, not an integer, so j > tL and x - x' is a zero of hat mu at level j - tL. One point of each class mod M b^((t+1)L) met inside a class mod M b^(tL) thus gives integers incongruent mod b^L with orthogonal differences; if g_L bounds their number, Lambda meets at most C M g_L^(ceil(n/L)) classes mod b^n, C its number of cosets of Q, and the class count gives k^n <= C M g_L^(n/L + 1) for every n, so g_L >= k^L. A zero of hat F off the roots of unity costs only the constant C.

Proved. If every A_n is a set and mu_{b,F} is spectral, then k <= b and Z(F) holds an order whose primes all divide b; otherwise hat mu has no integer zero, g_1 = 1 < k, and mu_{b,F} is not spectral. When Z(F) is empty no set hypothesis is needed: hat mu has no rational zero, so a spectrum through 0 holds at most one point in each of its finitely many cosets of Q and is finite, while L^2(mu) is infinite-dimensional, the support of mu being infinite. So mu_{b,{0,1,3,5,6}} is not spectral at any integer base b >= 2, bases 5 and 6, where levels repeat points, included: the mask 1 + x + x^3 + x^5 + x^6 has no cyclotomic factor (converse of lab/py/measure-spectra). An-He-Lai Example 5.2 takes a real ratio 0 < rho < 1 and believes no mu_{rho,{0,1,3,5,6}} is spectral; this proves it at every integer ratio rho = 1/b, a non-integer rho^(-1) stays open. A search of the other work of An, He and Lai, the arXiv listings on spectral self-similar measures with more than four digits, and the papers on product-form Hadamard triples finds neither this integer case nor a converse at prime digit count in print; that is a search, not a proof of absence. The same corollary rebuilds the non-spectrality of {0, 2} at odd base, where Z = {4} has no order with primes in b; Jorgensen and Pedersen prove more, at most two orthogonal exponentials.

Proved (one level). Let m be in Z(F) with every prime of m dividing b, and j(m) the least j with m | b^j. If b does not divide d and d reaches m at level j, then j = j(m) and v_q(d) = j(m) e_q - v_q(m) for every prime q of m. For q | b, v_q(m) = j e_q - min(v_q(d), j e_q), and m | b^j gives j >= j(m). Some q has v_q(d) < e_q; it divides m, since otherwise v_q(d) >= j e_q; so (j - 1) e_q < v_q(m) <= j(m) e_q and j < j(m) + 1. So integers pairwise incongruent mod b whose differences all reach m have every difference of one q-adic valuation, and number at most q, the least prime of m.

Proved (prime size). Let |F| = p be prime, 0 in F, every A_n a set, and F' = F/gcd(F).

  • The only prime power in Z(F') is p, and it is there exactly when F' is a complete residue system mod p; then every level tiles exactly when p | b.
  • Every other order in Z(F') has its least prime below p.
  • If mu_{b,F} is spectral, then some p integers, pairwise incongruent mod b, have every difference reaching an order of Z(F'); if one difference reaches p, every level tiles.
  • So if Z(F') holds at most one order that is not a prime power and has all its primes in b, then mu_{b,F} is spectral if and only if every level tiles.

Scaling keeps the measure spectral or not, the levels sets and every level tiling, so take F = F', which keeps 0 in F and has gcd(F) = 1; without 0 the statement fails, {1, 6, 11, 16, 21} at base 25 having Z(F') = {25} while every level tiles. A factor Phi_(q^a) makes F a union of q-fibres mod q^a by the tree lemma, so q = p and F is one class mod p^(a-1), which forces a = 1; then T1 holds with S_F = {p}, and the T1 section reads every level tiling as p | b. For another order m, Lam-Leung Theorem 4.8, read at source, writes F mod m as minimal vanishing sums, each a fibre of a prime of m or of weight above the third prime of m; if every prime of m were at least p, the weight p would leave one p-fibre, putting F in one class mod m/p against gcd(F) = 1. The integers are the integer orthogonal sets at L = 1. A difference reaching p makes p divide b^j, so p | b, and p is in Z(F). With one other order m available, if no difference reaches p, all reach m, and the one-level lemma caps the set at the least prime of m, below p; the forward direction is the theorem at prime-power size.

Verified. Over every digit set with 0 and gcd 1 in {0..b-1} of size 5 at bases 5 to 42, 7 at 7 to 26, 11 at 11 to 20 and 13 at 13 to 20, 803630, 654288, 167960 and 77520 sets, every level tiles on 8131, 784, 1 and 1, the verdict read as p in Z(F) by the first bullet, and on each of the others a clique search on Z/b, where d is an edge when its pattern mod each q^(e_q) is that of an order of Z(F) at its level, bounds the integers of the theorem by 3, below p; so on these boxes mu_{b,F} is spectral if and only if every level tiles. Of the non-tiling sets, 1674200 have no non-prime-power order with primes in b and 20085 have one, decided by the theorem above, and 196 have more, decided by the search alone (converse).

Refuted. The lemma that no p integers pairwise incongruent mod b have every difference reaching a non-prime-power order of Z(F'), which with the theorem above would give the converse at prime size from L = 1 alone. F = {0, 1, 251, 375, 501} at base 510 = 2 * 3 * 5 * 17 has residues {0, 0, 1, 1, 1} mod 5, so not every level tiles; mod 750 it is the 2-fibre {0, 375} and the 3-fibre {1, 251, 501}, and the same holds mod 150, 30 and 6, so 6, 30, 150, 750 are orders with primes in b, at levels 1, 1, 2, 3, and converse finds no other. The integers 0, 17, 1734, 1751, 176868 are pairwise incongruent mod 510, and every difference reaches 30 at level 1, 150 at level 2 or 750 at level 3 (converse). The orders at higher levels let the clique branch at three depths, each split simultaneous in the 2-adic and the 3-adic tree.

Proved (the covering bound). Let every A_n be a set and Q a set of primes meeting every order of Z(F) whose primes divide b; for q in Q let rho_q count the classes mod e_q met by v_q(m) over those orders m divisible by q. If mu_{b,F} is spectral, then k <= prod_{q in Q} q^(rho_q). Take the k^L integers of the integer orthogonal sets, pairwise incongruent mod b^L. A difference d reaching m at level j has m | b^j, so j >= j(m); some q' has v_q'(d) < L e_q', and either q' does not divide m and j e_q' <= v_q'(d) gives j < L, or (j - L) e_q' < v_q'(m) <= j(m) e_q'; so j < J + L with J the largest j(m). For q in Q dividing m, v_q(d) = j e_q - v_q(m) lies in [0, (J + L) e_q) and in one of rho_q classes mod e_q, so it takes at most rho_q (J + L) values. Every difference reaches an order divisible by some q in Q, and two of the integers whose difference has q-adic valuation delta differ in their q-adic digit at position delta, so their digits at those positions, over q in Q, tell all of them apart: k^L <= prod_q q^(rho_q (J + L)) for every L. The witness above has Q = {2} and v_2(m) = 1 on all four orders, so rho_2 = 1, 5 > 2, and its measure is not spectral; {0, 1, 9, 10} at base 12, which at L = 1 has the four integers 0, 2, 8, 10 incongruent mod 12 with orthogonal differences though T1 reads 4 against Phi_2(1) = 2, has orders 2, 6, 18, all with v_2 = 1, and covering bound 2 < 4.

Proved (five digits). If |F| = 5, 0 is in F and every A_n is a set, then mu_{b,F} is spectral if and only if every level tiles. Take gcd(F) = 1 and suppose not every level tiles; by the prime-size theorem no order of Z(F) with primes in b is a prime power. For such an order m, Lam-Leung Theorem 4.8 writes F mod m as minimal vanishing sums, each a fibre of a prime of m or of weight above the third prime, at least 6; the weight 5 is a single 5-fibre, which puts F in one class mod m/5, so m/5 divides gcd(F) = 1 and m = 5 is a prime power, or a 2-fibre and a 3-fibre. So F = P ∪ T with the pair P differing by m/2 and the triple T by m/3 mod m: v_2(m) = v_2(d_P) + 1 for the difference d_P of P, and T lies in one class mod 2^(v_2(m)). Two such splittings (P, T), (P', T') with exponents a, a' have a = a'. If P' = P, both equal v_2(d_P) + 1. If P' ⊂ T then P ⊂ T', and a - 1 >= a', a' - 1 >= a cannot both hold. Otherwise P = {f_1, f_2}, P' = {f_1, f_3} with f_3 in T, f_2 in T', and some f_4 in T ∩ T'; in f_1 - f_2 = (f_1 - f_3) + (f_3 - f_4) + (f_4 - f_2) the terms have 2-adic valuations a' - 1, at least a, at least a', so a' < a would give a - 1 = a' - 1, and a' > a fails with the roles exchanged. So every order of Z(F) with primes in b is even with one exponent of 2, and the covering bound with Q = {2}, rho_2 <= 1, reads 5 <= 2 (at odd b no order has its primes in b, and the bound is 1): the measure is not spectral. The forward direction is the theorem at prime-power size.

Proved. If F passes the T1 condition, in particular if every level tiles, its covering bound is at least |F|. Each p with Z_p(F) nonempty divides b, so the orders p^c, c in Z_p(F), have their primes in b; a covering set Q contains p, and rho_p >= |Z_p(F)| since those c are pairwise incongruent mod e_p; so the bound is at least prod_p p^(|Z_p(F)|) = |F|.

Verified. On the census boxes above the covering bound is below p on every non-tiling set, 795499, 653504, 167959 and 77519 of them; over every four-digit set with 0 and gcd 1 in {0..b-1} at bases 4 to 36, it is below 4 on all 48897 that do not tile at every level, so the bound alone gives the necessity half of the An-He-Lai classification on that box (converse).

Conjecture. The covering bound of F at base b is at least |F| exactly when F passes the T1 condition. Checked on every gcd-1 set with 0 in {0..b-1} of the census boxes at sizes 4, 5, 7, 11 and 13, of size 6 at bases 30 and 42, 8684 and 49566 passing and 107942 and 682990 failing, and of size 8 at base 24, 2188 passing and 242638 failing (converse). With the covering bound it would make a spectral measure whose levels are sets pass the T1 condition, which is the converse at every prime-power size and leaves only T2 at the other sizes.

The converse at prime size is proved at p <= 5, by An-He-Lai at 2 and 3 and above at five digits with 0 in F and levels that are sets, and decided on every census set at 7, 11 and 13. Above 5 the proof stops at the existence of a covering set: for p = 7 every non-prime-power order is even, but F mod m may split into fibres as 2 + 5 or 2 + 2 + 3, and asymmetric parts at orders divisible by 30 are not excluded here, so the splittings are not shown to share one exponent of 2, and rho_2 <= 2, enough since 4 < 7, is not proved; for larger p no prime common to all such orders is shown.

The gap

What the sections above leave open in dimension one, from tiling levels to a spectrum, is a size p^alpha q^beta with alpha, beta >= 1 and alpha + beta >= 3, or a size with three or more primes, together with an exponent above e_p after the gcd, where the Hadamard window does not reach; the converse is taken up at the end of this section. The stage form still decides such a design when it applies: cut digits into windows of base b_P, the part of b on the primes of |F|, scale window j by (b/b_P)^(K-j), and check An-Lai's conditions directly, as for the pq design {0, 1} ⊕ 12{0, 1, 2} at base 30, with windows 5{0, 1} and {0, 2, 4} and window spectra L^(0) = {0, 15}, L^(1) = {0, 5, 10}.

Verified. Over every digit set with 0 at bases 2 to 16 of a size dividing the base, and at bases 17 to 30 of size 4, 8, 9 or of a size with two distinct prime factors dividing the base, leaving out the cells size 8 and 12 at base 24, size 9 at base 27, size 14 at base 28 and sizes 10 and 15 at base 30, 6898 designs tile at every level: 6844 carry a Hadamard triple (b, F', L) after the gcd, 54 are in stage form for F or F', 40 of prime-power size and 14 of size 6 at base 30, and none is neither. So every one of them has a spectral measure, by Łaba-Wang Theorem 1.2 or An-Lai Theorem 2.4 (census of lab/py/measure-spectra).

Proved. The cells left out hold no design that tiles at every level and is neither in the Hadamard window after the gcd nor in stage form. Size 8 at base 24 is a prime-power size, where the construction of the theorem above is a stage form; base 27 is a prime-power base, where the T1 section puts every such design in the window. In the cells of a size with two distinct prime factors, where the claim is that no such design lies outside the window, every level tiling gives T1 and T2 for F, and the distinct cyclotomic factors of F have total degree at most b - 1. Size 12 at base 24 outside the window needs c_2 >= 4 or d >= 2 in Z_2 = {c_1, c_2}, Z_3 = {d}, and the factors at 2^(c_1), 2^(c_2), 3^d, 2^(c_1) 3^d, 2^(c_2) 3^d have degree at least 27 > 23. Size 14 at base 28 needs an exponent of 2 at least 3, and Phi_8 Phi_7 Phi_56 has degree 34 > 27, while Phi_49 alone has 42. Size 15 at base 30 needs Phi_9 Phi_5 Phi_45, degree 34 > 29, or Phi_25 Phi_75, more. Size 10 at base 30 has Z_5 = {1}, since Phi_25 Phi_50 has degree 40; Z_2 = {c} with c >= 4 costs Phi_16 Phi_80, degree 40; c = 3 needs Phi_8 Phi_5 Phi_40 and, for the T2 instance 200 at level 2, Phi_20 (the other witness Phi_200 has degree 80), degree 32 > 29; c = 2 needs Phi_4 Phi_5 Phi_20 and, for the instance 100 at level 2, Phi_10, so the counts of F mod 20 have a transform carried by the orders 1 and 2, every element of F is even, and F/2 has Z_2 = {1}, inside the window.

A falsifier would be a design whose every level tiles while every candidate spectrum fails completeness. At prime-power size and at pq digits none exists by the theorems above, and the census finds none at the other sizes it reaches. The pq proof stops at p^alpha q^beta with alpha, beta >= 1 and alpha + beta >= 3: the fibre lemma then allows p-fibres and q-fibres together, since p^alpha q^beta = p A + q B has several solutions, and T1 gives several exponents to one prime, so dividing by the gcd no longer forces an exponent 1, and the groups x_j need not be distinct mod q. The obstruction sits between windows: a stage-form sum E_0 ⊕ E_1(d) has a product mask, so a factor Phi_(p^a q^c) with p^a from one window and q^c from another must already divide one window's set, while T2 at every level asks the digit set for such composite factors across windows.

Conjecture. If every level of F at base b tiles, then F/gcd(F) carries an integer Hadamard triple at base b or F or F/gcd(F) is in An-Lai stage form with windows of base b_P, and mu_{b,F} is spectral; checked on every design at bases 2 to 16 and on sizes 4, 8, 9 and two-prime sizes at bases 17 to 30.

The converse, from a spectral measure to tiling levels, is decided at four digits or fewer by An-He-Lai; at five digits with 0 in F and levels that are sets by the covering bound of the section above; at other prime sizes, with 0 in F and levels that are sets, it is proved when at most one non-prime-power order of Z(F') has its primes in b, and decided on the census; at other sizes the covering bound is a necessary condition, which at four digits alone gives the An-He-Lai necessity on the census.

The paper Spectral Measures from Tiling Levels writes the limit-measure sections out for an outside reader: the window, the level shift with both spectra, the prime-power and pq theorems, the four-digit translation, and the converse through the covering bound with the five-digit theorem.

In dimension two the Hadamard triples of Dutkay, Haussermann and Lai give spectral self-affine measures in every dimension, so the window statement has a plane analogue, but the Coven-Meyerowitz conditions have no counterpart on Z^2 to read the tiling side; the plane codes are not decided here.

The census

The census runs every digit set containing 0 with at least two digits at every base from 2 to 16, 65519 sets, and prints per base the number that tile Z/b, the number that tile at every level, the number that pass the T1 condition, the counterexamples to the guess before and after the gcd, the T2 horizon and the histogram of tiling depths (census). The totals: 588 tile Z/b, 609 tile at every level, 641 pass the T1 condition; the 32 that pass it and fail T2 are all of size 6 at base 12, and fail already at level 1. At a prime base only the full digit set tiles every level, since the size must divide the base. Every tiling verdict at levels up to 3 and bases up to 12, 803 of them, carries a Coven-Meyerowitz complement whose sum with the level is checked to cover every residue mod lcm(S) once, and 492 levels at bases up to 8 and levels up to 2 agree with an exhaustive complement search over Z/N, |A| | N <= 512, which finds a complement for every tiling verdict and none for the others; two more levels pass the search's step cap (search).

Literature

  • Coven and Meyerowitz, the T1 and T2 conditions, Theorems A, B1 and B2, the scaling lemma 1.4, the residue lemma 1.3 and the period lemmas 2.1 and 2.3, read at source on arXiv; the index lemma generalises their Lemma 1.1(7).
  • Łaba, Theorem 1.5: T1 and T2 give a spectrum; a spectrum inside p^(-alpha) Z forces a prime-power size and T1.
  • Łaba and Wang, Theorems 1.2 to 1.4 with Lemmas 2.1 to 2.3, Lemma 2.2(b), (d) among them, and the proof of Theorem 1.4: a compatible pair gives a spectral measure, Lambda(N, S) is a spectrum unless a cycle of nonzero integers exists, and a complementing set mod b with at most two prime factors in its size gives a spectral measure; Conjecture 3.1.
  • An and Lai, Adv. Math. 431 (2023) 109257, Definitions 1.5, 2.1 and 2.3, Theorems 2.2 and 2.4, Examples 1.3 and 1.6 and the reductions of Section 3: product-form Hadamard triples of one and of k stages give spectral measures.
  • An, He and Lai, Section 1.1, Theorems 1.7, 4.2 and 5.1 with the sufficiency proof of Section 4.1: the spectral self-similar measures with at most four maps; Conjecture 1.6, a modified Łaba-Wang conjecture; Example 5.2 and the closing remark of Section 5: five digits open, {0, 1, 3, 5, 6} with irrational zeros only.
  • Jorgensen and Pedersen, Section 6 and Theorem 6.1: base 4 spectral, odd base at most two orthogonal exponentials.
  • Dai, He and Lau, Theorem 1.1: mu_{1/q, {0..N-1}} is spectral if and only if N | q; Section 6 restates the Łaba-Wang conjecture.
  • Dutkay, Haussermann and Lai: Hadamard triples give spectral self-affine measures in every dimension, read in the abstract.
  • Liu, Wang and Zheng, an unrefereed arXiv preprint, Section 1.1, Theorem 1.3 and the proof of Theorem 3.5: the spectral classification of {0..N-1} + m{0..L-1} and the decomposition of the level shift.
  • Wu and Xiao, Section 1: the question whether a spectral Cantor-Moran measure has tiling levels, and its answer for equidifferent digit sets.
  • Lam and Leung, Theorems 2.2, 3.1, 3.3 and 4.8 with Corollary 3.4: a vanishing sum of N-th roots of unity with non-negative coefficients is a non-negative combination of p-fibres and q-fibres when N = p^alpha q^beta, after de Bruijn; a minimal vanishing sum is a single fibre or has at least three primes and weight above the third prime.
  • An and Wang, J. Funct. Anal. 280 (2021) 108821, not read here: its publisher listing describes a characterisation of the spectral self-similar measures associated with an integer tile; Liu-Wang-Zheng Section 1.1 quote its Theorem 1.7 on strict product-form digit sets with respect to pq, which may overlap the pq theorem.
  • Li, Wu, Hu, Wang, Wang and Zhu, an unrefereed arXiv preprint, abstract read: it claims that T1 and T2 characterise the integer tiles of every size, so that every tile satisfies T2; a preprint is not a theorem here, and the statements above that call this open stand.

Generators

  • lab/py/level-tiles, one file, seven verbs: hand, index, census, search, witness, spectral, measure, about 90 seconds in all; its README maps every number on this page to its verb.
  • lab/py/measure-spectra, one file, six verbs: census, four, spectra, hunt, pq, converse, about 320 seconds in all; the Hadamard window, the stage form, the explicit spectra, the four-digit check, the pq product form and the prime-size converse.
  • The plane codes at dim 2, the limit measure at a size p^alpha q^beta with alpha, beta >= 1 and alpha + beta >= 3 or with three or more primes beyond the census, and the converse at five digits when some level repeats a point, and beyond five digits save at prime size with set levels and at most one non-prime-power order in b and on its census, are not decided here.