DIFFERENCE SETS AND ALGEBRAIC NUMBER THEORY

AN EXPOSITION OF SOME RESULTS OF SCHMIDT

GREGORY PRICE

Several combinatorical problems reduce to classifying certain families of difference sets. Schmidt, in [1], obtained strong new nonexistence results for this class of problem by applying algebraic number theory: a difference set can be related to a cyclotomic integer with bounded coefficients and a prescribed absolute value, and in many cases these integers can be number-theoretically proven not to exist. We lay out the core of Schmidt’s results, simplifying what we can and omitting some of the less interesting details.

1. Difference Sets

A (v, k, λ, n)-difference set in a group G of order v is a k-subset D ⊂ G such that each nonzero element of G has exactly λ representations as the difference of elements in D, with n = k − λ.

For instance, a Hadamard matrix is an m × m matrix H with entries ±1 satisfying H^{T} H = mI. If we identify the row and column indices in the matrix with elements of an order-m group G, then a G-invariant Hadamard matrix is a Hadamard matrix with H_{g,h} = H_{fg,fh} for f, g, h ∈ G. Such a matrix is described by the entries H_{1,g}; if we let D ⊂ G consist of the elements g ∈ G with H_{1,g} = 1, then D is a difference set with v = m; with some work it turns out that n = m/4 if m > 2.

In particular, we may consider circulant Hadamard matrices—Hadamard matrices invariant under cyclic groups Z/mZ. Such matrices are known only for m = 1, 4; it is known that any others must be of the form 4u^{2} for some u. A conjecture holds that there exist no circulant Hadamard matrices of order greater than 4. The results described herein will rule out almost all u as candidates.

To study difference sets, we first describe a few preliminaries. We identify any set S ⊂ G with the element ∑_{g∈S} g of the integral group ring Z[G], and for any element A = ∑_{g∈G} a_{g}g of the ring write A^{(−1)} for ∑_{g∈G} a_{g}g^{−1}. A character of a finite abelian group G is a homomorphism χ : G → C^{∗} to the multiplicative group of nonzero complex numbers, hence to the group of e-th roots of unity for some e called the order of χ. We extend group homomorphisms G → H linearly to ring homomorphisms Z[G] → Z[H].

Date: 2004-05-24.

Now the condition that D be a difference set becomes

DD^{(−1)} = n + λG.

If we require G to be abelian and apply any nontrivial character χ of G to this equation we obtain

χ(D)\overline{χ(D)} = n

since χ(G) = 0. A bit more generally, if we take a normal subgroup U of G with G/U abelian and ρ : G → G/U the quotient map, then

ρ(D)ρ(D)^{(−1)} = n + λ|U|(G/U)

so for any nontrivial character χ of G/U

χ(ρ(D))\overline{χ(ρ(D))} = n.

So, writing X for χ(ρ(D)), X\overline{X} = n. But X is a very particular sort of number; it’s a cyclotomic integer, writable as X = ∑_{i} a_{i}ζ_{m}^{i} where 0 ≤ a_{i} ≤ |U| and m is the order of χ. For any particular U and m, there are only finitely many of these, so the condition X\overline{X} = n will turn out to be a restrictive one. We can use this to rule out classes of difference sets.

2. Bounding the Absolute Value of Cyclotomic Integers

We’ll be concerned with the following version of the remaining problem: given a cyclotomic integer X = ∑_{i} a_{i}ζ_{m}^{i} ∈ Z[ζ_{m}] with |a_{i}| < C, for what n ∈ Z can X\overline{X} = n? For instance, by the triangle inequality, the complex absolute value of X = ∑_{i} a_{i}ζ_{m}^{i}, |a_{i}| ≤ C, is at most mC, so its square X\overline{X} is at most m^{2}C^{2}. We thus have a bound on the possible values of X\overline{X}; we’ll find others. For clarity we write the bounds we obtain as

X\overline{X} = n ≤ M(m, n)C^{2}

(since they must scale quadratically with C); thus the bound we’ve already obtained is M(m, n) = m^{2}.

(Observe that we’ve given up the information that a_{i} ≥ 0, which is true of all the cases arising from difference sets above. A careful analysis, keeping this information, gains about a factor of 2 in the bound M obtained, but complicates the results that answer this question and the results that use the answer. For our purposes this isn’t worth the loss in clarity.)

A sufficiently tight answer to this problem will allow us to rule out many possibilities for difference sets:

Proposition 2.1. Let a group G contain a (v, k, λ, n)-difference set D, and let U be a normal subgroup of G with G/U cyclic of order e and ρ : G → G/U be the quotient map. Then with M(m, n) as above, we have

e ≤ (\frac{M(e, n)}{n})^{1/2} v.

Proof. Let χ be a character of order e on G/U. Since the homomorphism χ ∘ ρ has kernel of order v/e, the image of D can be written χ(ρ(D)) = ∑_{i=0}^{e−1} a_{i}ζ_{e}^{i} with 0 ≤ a_{i} ≤ v/e and in particular |a_{i}| ≤ v/e. Hence

n = χ(ρ(D))\overline{χ(ρ(D))} ≤ M(e, n)\frac{v^{2}}{e^{2}}

which leads immediately to the result. □

We can be a bit more explicit in the abelian case, which follows immediately:

Proposition 2.2. Let an abelian group G contain a (v, k, λ, n)-difference set D. Then with M(m, n) as above, we have

exp G ≤ (\frac{M(v, n)}{n})^{1/2} v

where the exponent exp G of an abelian group G is the order of its largest cyclic subgroup.

In particular, if we have a circulant Hadamard matrix of order m = 4u^{2}, then exp G = v = 4u^{2} and n = u^{2}, so that

u ≤ M(4u^{2}, u^{2})^{1/2}.

Unfortunately, these results have little use for the trivial bound M(m, n) = m^{2} found above; the resulting version of (2.1) is

n ≤ v^{2}

which is uninteresting since in any case n ≤ k ≤ v. We’ll need a better bound.

However, but for a constant factor, no better bound will come without using more specific information from the situation we’re interested in. Indeed, taking X = 1 + ζ_{m} + ζ_{m}^{2} + ⋯ + ζ_{m}^{⌊m/2⌋} gives for large m a norm |X| ≃ \frac{m}{π}, so that X\overline{X} ≈ π^{−2}m^{2}. What’s going wrong in this case?

3. The Norm is Rational

The first refinement we can make is to observe that the absolute values n we’re interested in are rational integers. This means that once the absolute value is written in a basis (rather than the more-than-basis {ζ_{m}^{i}}_{i=0,··· ,m−1}), only the coefficient on 1 may be nonzero, and so the bound on each coefficient becomes a bound on the whole sum. It is straightforward to show that a bound k on the coefficients in the more-than-basis implies a bound 2^{δ(m)}k on the coefficients in the basis, where δ(m) is the number of distinct prime divisors of m. The bound on the more-than-basis coefficients in X\overline{X} is C^{2}m, so

X\overline{X} ≤ 2^{δ(m)}mC^{2},

and

M(m, n) = 2^{δ(m)}m

works.

This, unfortunately, still gives us little in (2.1); the resulting inequality is

ne2^{−δ(e)} ≤ v^{2}

which is still uninteresting since in any case ne2^{−δ(e)} ≤ v · v · 1 = v^{2}.

This refinement, however, will help us after we make another one; and the fact that our n of interest are rational will be essential in making the latter.

4. A Smaller Field

It turns out that for most m and n, if X\overline{X} = n lies in Z for some X ∈ Z[ζ_{m}], then X in fact lies, up to multiplication by a root of unity, in a much smaller cyclotomic field Z[ζ_{f}]. A bit more precisely,

Theorem 4.1. If X ∈ Z[ζ_{m}] satisfies X\overline{X} = n ∈ Z, then in fact X ∈ ζ_{m}^{j}Z[ζ_{F (m,n)}] for some j, where F is a function to be defined.

It will turn out that F is usually on the order of the squarefree part of m. The proof of this depends on the following lemma, the most algebraic-number-

theoretical of the results discussed in this paper. The decomposition group of a prime P in a Galois extension K/L is the subgroup of σ in the Galois group with P^{σ} = P.

Lemma 4.2. Let P | p be prime ideals in Z[ζ_{m}], Z respectively, and write m = p^{a}m′ with p ∤ m′. Then the decomposition group of P over Q consists of exactly those σ ∈ Gal(Q(ζ_{m})/Q) that for some j satisfy

σ(ζ_{m′}) = ζ_{m′}^{p^{j}}.

Now write m = ∏_{i} p_{i}^{c_{i}}. We will define in terms of m and n a sequence of exponents b_{i} ∈ {1, …, c_{i}} that are as small as we can make them while keeping the properties we need. We’ll then outline a proof that for each F_{i} = m/p^{c_{i}−b_{i}} we can write X as a p^{c_{i}}-th root of unity ξ_{i} (i.e. an element of the F_{j}, j ≠ i) times an element of Z[ζ_{F_{i}}]. Writing ξ = ∏_{i} ξ_{i} then gives Xξ ∈ Z[ζ_{F_{i}}] for all i, so Xξ ∈ ⋂_{i} Z[ζ_{F_{i}}] = Z[ζ_{F}] where F = gcd_{i} F_{i} = ∏_{i} p_{i}^{b_{i}}.

The property we need the b_{i} to satisfy concerns automorphisms σ_{i} : ζ_{m} ↦ ζ_{m}^{1+F_{i}}: each σ_{i} must stabilize each prime ideal in Z[ζ_{m}] lying over n. By the lemma on decomposition groups in cyclotomic fields, this is true if, for each prime q | n and each i, ζ_{M_{q}}^{1+F_{i}} = ζ_{M_{q}}^{q^{l}} for some power l, where M_{q} = ∏_{p_{j}≠q} p_{j}^{c_{j}}. In other words, we need 1 + F_{i} ≡ q^{l} (mod M_{q}); if p_{i} = q then l = 0 suffices, and otherwise we split this congruence into primes by the Chinese Remainder Theorem to obtain

1 + p_{i}^{b_{i}} ≡ q^{l} (mod p_{i}^{c_{i}})
1 ≡ q^{l} (mod p_{j}^{c_{j}}) (p_{j} ≠ p_{i}, q)

For p_{i} odd, we define b_{i} to be the least integer such that these congruences are solvable. (We omit the case p_{i} = 2 for simplicity; it’s a bit more complicated since the multiplicative groups modulo powers of 2 are in general not cyclic.) This is at most c_{i}, since b_{i} = c_{i} makes l = 0 work. Otherwise, it’s the exact power to which p_{i} divides one less than the first power of q satisfying 1 ≡ q^{l} (mod p_{j}^{c_{j}}) for all j (which makes this power of q generate the group of 1 + kp_{i}^{b_{i}} modulo p_{i}^{c_{i}}.)

Now, since the σ_{i} stabilize each prime lying over n and since X\overline{X} = n so that each prime dividing X divides also n, the σ_{i} stabilize X. Hence each X^{σ_{i}} is X times a unit ε_{i} of Z[ζ_{m}]. With some work it can be shown that this unit is in fact a root of unity; with some further work using only elementary modular arithmetic it can be shown that multiplying X by a suitable p_{i}^{c_{i}}-th root of unity ξ_{i} eliminates this unit factor and produces an Xξ_{i} which is fixed by σ_{i}. So Xξ_{i} lies in the fixed field of σ_{i}. This field certainly contains Q(ζ_{F_{i}}), since ζ_{F_{i}}^{σ_{i}} = ζ_{F_{i}}^{1+F_{i}} = ζ_{F_{i}}; and by counting dimensions and applying the fundamental theorem of Galois theory, this is the entire fixed field. So Xξ_{i} lies in Q(ζ_{F_{i}}) and hence, being an integer, in Z[ζ_{F_{i}}].

We’ve now proven Theorem 4.1 modulo the lemma on decomposition groups, the case p_{i} = 2, and the details of showing that X^{σ_{i}} = Xε_{i} implies the existence of ξ_{i} with (Xξ_{i})^{σ_{i}} = Xξ_{i}.

To apply this result to our main problem, it’s some straightforward work to show that a bound C on the coefficients of X as a sum of powers of ζ_{m} implies the same bound C on its coefficients as a sum of powers of ζ_{F (m,n)}, using the fact that F (m, n) contains all the same primes as m; then applying the result of Section 3 gives

X\overline{X} ≤ 2^{δ(F (m,n))}F (m, n)C^{2} ≤ 2^{δ(m)}F (m, n)C^{2},

so that

M(m, n) = 2^{δ(m)}F (m, n)

works. The resulting version of (2.1) is

e ≤ (\frac{2^{δ(e)}F (e, n)}{n})^{1/2} v

and in the circulant-Hadamard case

2u ≤ 2^{δ(2u)/2}F (4u^{2}, u^{2})^{1/2}.

It remains to see just how much good this actually does us—nothing yet said has suggested that F (m, n) is in general much smaller than m itself, though by definition it can be no larger.

4.1. How Much Smaller? The first observation we can make about F (m, n) is that it is independent of the powers to which primes occur in n and nearly so in m; indeed, for any finite set of primes there is a finite bound on the value of F (m, n) for m, n products of powers of primes in the set. Hence for any choice of the primes making up m, n we can make F (m, n) much smaller than m, n by taking these primes to large powers.

We can be a bit more specific by accepting some heuristicity, and by restricting to a common case. Write m_{0} for the squarefree part of m, and let n ≤ m, m ≈ m_{0}^{2}, where ‘≈’ is used loosely. We’ll show that for most such m, n, none of the large prime divisors of m will occur more than once in F (m, n). Schmidt claims in [1] that this makes F (m, n) of the order of m_{0} for such m, n. It’s not obvious to me that it implies anything of the kind, especially since Schmidt defines the ‘large’ primes as those that are larger than the expected average of the prime powers in the factorization of m, and these primes are precisely the ones that usually occur only once in m in the first place.

For a prime q | n, let q^{o_{mq} (q)} be the power of q appearing in the definition of the b_{i}, where m_{q} is the product of the p_{j} distinct from q. Fix a prime p_{i} | m. Then b_{i} > 1 just if

p_{i}^{2} | q^{o_{mq} (q)} − 1

for some q. Now o_{m_{q}}(q) | ϕ(q), and most p_{i} do not divide ϕ(q), so for any n it is unlikely that any large p_{i} divide o_{m_{q}}(q). In the remaining cases, Q ≡ 1 (mod p_{i}^{2}) only if q lies in the subgroup of (Z/p^{2}Z)^{∗} with order not divisible by p, which has p − 1 elements, a fraction 1/p of the total. Since large primes are nearly evenly distributed modulo each other, this happens a fraction 1/p of the time.

Now, excluding a set of density zero, any positive integer x has approximately log log x prime divisors. So outside of this set, we have no more than about (log log m)(log log n) ≈ (log log m_{0})^{2} pairs (p_{i}, q).

Now consider any ‘large’ p_{i}; Schmidt takes p_{i} ≥ m_{0}^{1/ log log m_{0}} = exp(\frac{log m_{0}}{log log m_{0}} ), but we may take instead p_{i} ≥ log m_{0} = exp(log log m_{0}), which is much smaller for large m_{0}. The probability that any of the divisions above for any of these primes holds is then at most (log log m_{0})^{2}/ log m_{0}, which goes to zero for large m_{0}. For large m_{0}, then, we might hope that only a few small primes occur more than once in F (m, n); i.e., that F (m, n) is not much bigger than m_{0}.

What does this heuristic bound do for us in (2.1)? For m ≈ n ≈ v and m_{0} ≈ m^{1/2}, we obtain

e ⪅ (\frac{2^{δ(e)}e^{1/2}}{n} )^{1/2} m

which in the abelian case becomes

e ⪅ 2^{δ(m)/2}m^{3/4} ≈ m^{3/4}

since δ(m) grows very slowly with m.

In the case of circulant Hadamard matrices, this bound is quite powerful indeed. For when it applies, it requires

m ⪅ m^{3/4}

which is false. Hence a circulant Hadamard matrix can only exist for m on which this bound fails. Indeed, a circulant Hadamard matrix can only exist if F (4u^{2}, u^{2}) is very nearly 4u^{2}, and our heuristics suggest this should very rarely be the case. As expected, an explicit application of the bound, without heuristics, succeeds in ruling out nearly all u for which it’s been tried; for instance, only 26 values of u less than 10000 are not ruled out, two between 10^{5} and 10^{5} + 10^{4}, and none at all between 10^{8} and 10^{8} + 10^{4}.

References

[1] B. Schmidt: Cyclotomic integers and finite geometry. J. AMS 12 (1999), 929–952.