401 and Beyond: Improved Bounds and Algorithms for the Ramsey Algebra Search

Jeremy F. Alm^{∗} Department of Mathematics Illinois College Jacksonville, IL 62650 USA

                alm.academic@gmail.com

Abstract

In this paper, we discuss an improvement of an algorithm to search for primes p and coset-partitions of (ℤ/pℤ)^{×} that yield Ramsey algebras over ℤ/pℤ. We also prove an upper bound on the modulus p in terms of the number of cosets. We obtain, as a corollary, that there is no prime p for which there exists a partition of (ℤ/pℤ)^{×} into 13 cosets that yields a 13-color Ramsey algebra.

1 Introduction

In this paper, we continue the project begun in Comer [5] and continued in two recent papers [2, 11] of constructing Ramsey algebras over ℤ/pℤ using multiplicative cosets. A Ramsey algebra in m colors is a partition of a set U ×U into disjoint binary relations Id, A_{0}, …, A_{m−1} such that

(I) A_{i}^{−1} = A_{i};

(II) A_{i} ∘ A_{i} = A_{i}^{c};

(III) for i ≠ j, A_{i} ∘ A_{j} = Id^{c}.

∗Author’s current address: Department of Mathematics, Lamar University, Beaumont, TX 77710, USA.

Here, Id = {(x, x) : x ∈ U} is the identity over U, ∘ is relational composition, ^{−1} is relational inverse, and ^{c} is complementation with respect to U × U.

Ramsey algebras are representations of relation algebras first defined in Maddux’s paper [14] (but not named). With the single exception of an alternate construction of the 3-color algebra using (ℤ/4ℤ)^{2} (see Whitehead’s paper [18]), all known constructions use the “guessand-check” finite-field method of Comer, as follows: Fix m ∈ ℤ^{+}, and let X_{0} = H be a multiplicative subgroup of 𝔽_{q} of order (q − 1)/m, where q ≡ 1 (mod 2m). Let X_{1}, … X_{m−1} be its cosets; specifically, let X_{i} = g^{i}X_{0} = {g^{am+i} : a ∈ ℤ^{+}}, where g is a generator of 𝔽_{q}^{×}. Suppose the following conditions obtain:

(i) −X_{i} = X_{i};

(ii) X_{i} + X_{i} = 𝔽_{q} \ X_{i},

(iii) for i ≠ j, X_{i} + X_{j} = 𝔽_{q} \ {0}.

Then define A_{i} = {(x, y) ∈ 𝔽_{q} × 𝔽_{q} : x − y ∈ X_{i}}. It is easy to check that (i)-(iii) imply (I)-(III), and we get a Ramsey algebra. Condition (ii) implies that all the X_{i}’s are sum-free. Consequently, the triangle-free Ramsey number R_{m}(3) is a bound on the size of prime powers q such that there might be an m-color Ramsey algebra over 𝔽_{q}. Most of the attention has been given to prime fields 𝔽_{p} = ℤ/pℤ, and we now restrict our attention to these.

Comer was able to construct m-color Ramsey algebras for m = 1, 2, 3, 4, 5 in 1983 [5]. In 2011, Maddux produced constructions for m = 6, 7 using the same method as Comer but with a 2011 computer [13]. Maddux failed to construct a Ramsey algebra for m = 8. In 2013, Manske and the author produced constructions over prime fields for all m ≤ 400, with the exceptions of m = 8 and m = 13. We were able to rule out m = 8 by checking all primes up through the Ramsey bound R(3, 3, 3, 3, 3, 3, 3, 3). Independently around that same time, Kowalski [11] produced constructions for all m ≤ 120 except for m = 8 and m = 13, and found some constructions over non-prime fields. He also ruled out m = 8 over non-prime fields by checking all prime powers up through the Ramsey bound. The case of m = 13 was left open. In the present paper, we give constructions for all 401 ≤ m ≤ 2000 using prime fields and prove an upper bound on p in terms of m that is much better than the Ramsey bound, allowing us to rule out m = 13 for prime fields.

In Section 2, we state some results we’ll be assuming. In Section 3, we give an improvement of the algorithm, using a recent insight. In Section 4, we prove bounds on p in terms of m. The method of proof of the upper bound comes from additive number theory. The first idea is that if a set is “unstructured” with respect to addition, then it should contain a solution to x + y = z, and hence not be sum-free. The second idea is that subsets of a field cannot be both additively structured and multiplicatively structured. Since X_{0} is a multiplicative subgroup, it is highly structured, so it must be additively unstructured, i.e., its elements are “randomly” distributed. This is an example of a so-called sum-product phenomenon. See Green’s survey [8]. Chung and Graham first studied quasirandom subsets of ℤ/nℤ in a 1992 paper [4]. They showed that several different measures of quasirandomness were equivalent. The measure that we will use in Section 4 is that of having small nontrivial Fourier coefficients.

For more background on relation algebras, the reader is directed to the author’s MS thesis[1] or two authoritative texts [10, 15].

2 Background from Alm-Manske

In order to give a more complete background, we repeat some lemmas from the author’s 2015 paper with Manske [2], condensed into one. The following lemma shows that, while multiplicative subgroups may appear randomly distributed, they and their cosets have some quite well-behaved sumset properties.

Lemma 1. Let m ∈ ℤ^{+} and let p = mk + 1 be a prime number with k even, and let g be a primitive root modulo p. For i ∈ {0, 1, …, m − 1}, define

X_{i} = {g^{i}, g^{m+i}, g^{2m+i}, …, g^{(k−1)m+i}} .

1. We have that X_{0} is sum-free if and only if 1 ∉ (X_{0} + X_{0});

2. If X_{0} + X_{0} = (ℤ/pℤ) \ X_{0}, then X_{i} + X_{i} = (ℤ/pℤ) \ X_{i} for all i ∈ {1, 2, …, m − 1}.

3. If X_{0} + X_{i} = (ℤ/pℤ) \ {0} for all i ∈ {1, 2, …, m − 1}, then ∀i ≠ j, X_{i} + X_{j} = (ℤ/pℤ) \ {0}.

Lemma 1 tells us that the sumset structure of the X_{i}’s has “rotational symmetry”, which reduces the number of things that must be checked. In particular, it suffices to consider only those set sums involving X_{0}.

3 Improvement of the algorithm from Alm-Manske

The following lemma affords us a way to check, given m and p ≡ 1 (mod 2m), whether the m cosets of size \frac{p−1}{m} form a Ramsey algebra.

Lemma 2. Let m ∈ ℤ^{+} and let p = mk + 1 be a prime number, k even, and g a primitive root modulo p. For i ∈ {0, 1, …, m − 1}, define

X_{i} = {g^{i}, g^{m+i}, g^{2m+i}, …, g^{(k−1)m+i}} .

If (X_{0} + X_{i}) ∩ X_{j} ≠ ∅, then (X_{0} + X_{i}) ⊇ X_{j}.

This lemma is very easy to prove and was apparently known to Comer, but it seems that no one previously saw how to use it to get an algorithmic improvement. The next corollary justifies the algorithm presented in the pseudocode below it. The algorithm is a special case of a more general one given in [3].

Corollary 3. Suppose (X_{0}−1)∩X_{0} = ∅, but for all i, j not both zero, we have (X_{0}−g^{j})∩X_{i} ≠ ∅. Then the X_{i}’s form a Ramsey algebra.

Data: A prime p, a divisor m of (p − 1)/2, a primitive root g modulo p Result: A Boolean, telling whether the corresponding coset structure is a Ramsey

algebra Compute X_{0} = {g^{am} (mod p) : 0 ≤ a < (p − 1)/m}; Compute g^{j} − X_{0} (mod p) for each 0 ≤ j < m; if (1 − X_{0}) ∩ X_{0} ≠ ∅ then

return False end for i ← 1 to m − 1 do

X_{i} = {g^{am+i} (mod p) : 0 ≤ a < (p − 1)/m} for j ← i to m − 1 do

if (g^{j} − X_{0}) ∩ X_{i} = ∅ then

return False end

end end return True

Algorithm 1: Fast algorithm for checking for Ramsey algebras

This algorithm is significantly faster. For example, Kowalski’s results (1 ≤ m ≤ 120, skipping 8 and 13) can be reproduced in 59 seconds.

For each m between 1 and 2000, we have found the smallest prime modulus over which Comer’s construction yields an m-color Ramsey algebra. The data are available in sequence \underline{A263308} in the On-Line Encyclopedia of Integer Sequences.

4 The Fourier transform, quasirandom sets, and a Ramseylike bound

Theorem 4. Let the m-color multiplicative-coset Ramsey algebra be constructible over ℤ/pℤ. Then for m > 6,

2m^{2} − 2m + 1 ≤ p ≤ m^{4} + 5

Proof. First we establish the lower bound by counting formal sums. Suppose p < 2m^{2}−2m+

1. Since (p − 1)/2 must be divisible by m, and (p − 1)/m must be even, p ≤ 2m^{2} − 4m + 1. We must have X_{0} + X_{0} = (ℤ/pℤ)\X_{0}, so |X_{0} + X_{0}| = p − (p − 1)/m; however, counting

formal sums we have

|X_{0} + X_{0}| ≤ \binom{⌊\frac{p−1}{m}⌋}{2} + ⌊\frac{p−1}{m}⌋ − \frac{1}{2} ⌊\frac{p−1}{m}⌋ + 1 = \frac{⌊\frac{p−1}{m}⌋2}{2} + 1

Figure 1: Computational data, with trendline Figure 2: Computational data, with bounds proven in Section 4

where the binomial coefficient is the number of sums of two distinct elements, ⌊\frac{p−1}{m}⌋ counts the number of self-sums, \frac{1}{2} ⌊\frac{p−1}{m}⌋ is a lower bound on the number of these sums that result in 0, and the 1 adds the identity back to the count.

Thus, it must be the case that

\frac{⌊\frac{p−1}{m}⌋2}{2} + 1 ≥ p − (p − 1)/m.  (1)

Then one may check that if p = 2m^{2} − 4m + 1, (1) fails to hold. Certainly, then, no smaller modulus will suffice.

We now turn our attention to the upper bound. It will suffice to show that for p > m^{4}+5, X_{0} is not sum-free. We take as our starting point the ideas of Roth, who first used Fourieranalytic techniques to count the number of solutions to a linear equation inside a set [16]. Fourier analysis in additive number theory has become a subfield in its own right since the seminal work of Gowers [6, 7], now sometimes called quadratic Fourier analysis. We need only the “linear” Fourier analysis of Roth. We follow the development in Lyall’s notes [12].

Suppose we want to count the solutions to the equation x + y = z inside a set A ⊆ ℤ/pℤ with |A| = δp. Let N be the number of solutions inside A. We have

\frac{1}{p} ∑_{k=0}^{p−1} e^{− \frac{2πik}{p} x} = \begin{cases}1, & if x ≡ 0 (mod p); \\ 0, & if x ≢ 0 (mod p). \end{cases}  (2)

Because of (2), we have

N = ∑_{x∈A} ∑_{y∈A} ∑_{z∈A} \frac{1}{p} ∑_{k=0}^{p−1} e^{− \frac{2πik}{p} (x+y−z)}  (3)

Rearranging (3), we get

\frac{1}{p} ∑_{k=0}^{p−1} ∑_{x∈A} ∑_{y∈A} ∑_{z∈A} e^{− \frac{2πik}{p} x} · e^{− \frac{2πik}{p} y} · e^{\frac{2πik}{p} z}

= \frac{1}{p} ∑_{k=0}^{p−1} [∑_{x∈A} e^{− \frac{2πik}{p} x} · ∑_{y∈A} e^{− \frac{2πik}{p} y} · ∑_{z∈A} e^{\frac{2πik}{p} z}]

= \frac{1}{p} ∑_{k=0}^{p−1} [ ∑_{x∈ℤ/pℤ} Ch_{A}(x)e^{− \frac{2πik}{p} x} · ∑_{y∈ℤ/pℤ} Ch_{A}(y)e^{− \frac{2πik}{p} y} · ∑_{z∈ℤ/pℤ} Ch_{A}(−z)e^{\frac{2πik}{p} z}]

= \frac{1}{p} ∑_{k=0}^{p−1} Ĉh_{A}(k)^{2} · Ĉh_{A}(−k),  (4)

where Ch_{A} denotes the characteristic function of A, and f̂ denotes the Fourier transform of f,

f̂(x) = ∑_{k=0}^{p−1} f(k)e^{− \frac{2πik}{p} x}.

Now we can pull out the k = 0 term from (4):

(4) = \frac{1}{p}Ĉh(0)^{3} + \frac{1}{p} ∑_{k=1}^{p−1} Ĉh_{A}(k)^{2} · Ĉh_{A}(−k)

= \frac{|A|^{3}}{p} + \frac{1}{p} ∑_{k=1}^{p−1} Ĉh_{A}(k)^{2} · Ĉh_{A}(−k)

= δ^{3}p^{2} + \frac{1}{p} ∑_{k=1}^{p−1} Ĉh_{A}(k)^{2} · Ĉh_{A}(−k).

If we selected elements from ℤ/pℤ at random and placed them in A, then we’d expect δ^{3}p^{2} solutions to x + y − z = 0 in A. In light of this, we call δ^{3}p^{2} the main term, and \frac{1}{p} ∑_{k=1}^{p−1} Ĉh_{A}(k)^{2} · Ĉh_{A}(−k) the error term. The error term will measure how close (or far) A is from being a “random” set. We now bound this error term.

Suppose 0 < α < 1 and |Ĉh_{A}(k)| ≤ αp for all 0 ≠ k ∈ ℤ/pℤ. In this case, we say that A is α-uniform. Then

|\frac{1}{p} ∑_{k=1}^{p−1} Ĉh_{A}(k)^{2} · Ĉh_{A}(−k)| ≤ \frac{1}{p} max |Ĉh_{A}(k)| · |∑_{k=1}^{p−1} Ĉh_{A}(k)^{2}|

≤ α |∑_{k=1}^{p−1} Ĉh_{A}(k)^{2}|

≤ αp |∑_{k=1}^{p−1} Ch_{A}(k)^{2}|

≤ αδp^{2},

where the second-to-last line is by Parseval’s identity.

Hence N ≥ δ^{3}p^{2} − αδp^{2}. So we want α < δ^{2}. By Schoen and Shkredov [17, Corollary 2.5], if H is a multiplicative subgroup of ℤ/pℤ, then H is α-uniform for α = p^{−1/2}. Now δ = \frac{p−1}{mp}, so α < δ^{2} is equivalent to (p−1)^{4} > m^{4}p^{3}, which in turn is equivalent to p > m^{4} +5 for integers p > 6. Therefore X_{0} is δ^{2}-uniform, so it contains a solution to x + y = z and hence is not sum-free.

Note that the upper bound given in Theorem 4 is significantly less than what one gets by using the Ramsey number R_{m}(3), which is at least exponential in m.

Corollary 5. There is no 13-color multiplicative-coset Ramsey algebra constructible over ℤ/pℤ for any prime p. Hence \underline{A263308}(13) = 0.

Proof. Let m = 13. Then by Theorem 4, p < 28567. We have verified that no such prime yields a 13-color multiplicative-coset Ramsey algebra.

Note that using the upper bound on R_{13}(3) from Greenwood and Gleason [9] would have required checking primes up through 1.69 · 10^{10}.

In Figure 3 below, one can see the normalized maximum modulus of the nontrivial Fourier coefficients of the characteristic function of X_{0} over candidate primes p for m = 13. As p (and hence |X_{0}|) grows, this maximum modulus shrinks relative to p. Hence X_{0} is more and more “random-looking”. The red horizontal line indicates the threshold for our method to guarantee that X_{0} is not sum-free.

(a)  (b)

Figure 3: Normalized maximum modulus of nontrivial Fourier coefficients of Ch(X_{0}). The red line is y = 1/δ^{2} = 1/169. One can see that as p increases, the X_{0}’s become increasingly uniform.

5 Further directions

While there has been significant computational progress on this problem in the last few years, computation will never get us a proof that Ramsey algebras are constructible for all sufficiently large m. We hope that the ideas in the proof of Theorem 4 are a significant step in this direction. We now collect some open problems whose resolution would contribute to such a proof.

Problem 1. Prove estimates on the number of primes p ≡ 1 (mod 2m) between 2m^{2} and m^{3}.

Problem 2. For certain primes p significantly smaller than m^{4}, X_{0} is not sum-free. Find conditions on p and m that suffice for X_{0} to be sum-free.

Problem 3. Improve the Ramsey-like upper bound in Theorem 4. For example, it would seem reasonable to think that one could do better than p^{−1/2}-uniformity, which holds for all subgroups, by taking into account that the X_{0}’s are relatively large.

6 Acknowledgments

I wish to thank Jacob Manske and David Andrews for many useful conversations; Andy Ylvisaker, who made an important observation concerning the algorithm; Illinois College trustee Del Dunham, whose generous donation allowed me to purchase my new computeserver; and Keenan Mack, whose collaboration and friendship kept me sane this past academic year.

References

[1] Jeremy F. Alm, On sets of first-order formulas axiomatizing representable relation algebras. M.S. Thesis, Iowa State University, 2004. Available at

https://arxiv.org/abs/1604.08227.

[2] Jeremy F. Alm and Jacob Manske, Sum-free cyclic multi-bases and constructions of Ramsey algebras, Discrete Appl. Math. 180 (2015), 204–212.

[3] Jeremy F. Alm and Andrew Ylvisaker, A fast coset-translation algorithm for computing the cycle structure of Comer relation algebras over ℤ/pℤ, preprint, 2017,

https://arxiv.org/abs/1708.04974.

[4] F. R. K. Chung and R. L. Graham, Quasi-random subsets of Z_{n}, J. Combin. Theory Ser. A 61 (1992), 64–86.

[5] S. D. Comer, Color schemes forbidding monochrome triangles, In Proceedings of the Fourteenth Southeastern Conference on Combinatorics, Graph Theory and Computing, Congr. Numer. 39 (1983), 231–236.

[6] W. T. Gowers, A new proof of Szemerédi’s theorem for arithmetic progressions of length four, Geom. Funct. Anal. 8 (1998), 529–551.

[7] W. T. Gowers, A new proof of Szemerédi’s theorem, Geom. Funct. Anal. 11 (2001), 465–588.

[8] B. Green, Sum-product phenomena in 𝔽_{p}: a brief introduction, 2009. Available at

https://arxiv.org/abs/0904.2075.

[9] R. E. Greenwood and A. M. Gleason, Combinatorial relations and chromatic graphs, Canad. J. Math. 7 (1955), 1–7.

[10] R. Hirsch and I. Hodkinson, Relation Algebras by Games, Vol. 147 of Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Co., 2002.

[11] Tomasz Kowalski, Representability of Ramsey relation algebras, Algebra Universalis 74 (2015), 265–275.

[12] N. Lyall, Roth’s theorem: the Fourier-analytic approach. Available at

    http://alpha.math.uga.edu/~lyall/REU/Roth.pdf.

[13] R. Maddux, Do all the Ramsey algebras exist? Talk presented at the AMS sectional meeting in Iowa City, March 18 2011.

[14] R. Maddux, Some varieties containing relation algebras, Trans. Amer. Math. Soc. 272 (1982), 501–526.

[15] R. Maddux, Relation Algebras, Vol. 150 of Studies in Logic and the Foundations of Mathematics, Elsevier, 2006.

[16] K. F. Roth, On certain sets of integers, J. London Math. Soc. 28 (1953), 104–109.

[17] Tomasz Schoen and Ilya D. Shkredov, Additive properties of multiplicative subgroups of 𝔽_{p}, Q. J. Math. 63 (2012), 713–722.

[18] Earl Glen Whitehead, Jr., Difference sets and sum-free sets in groups of order 16, Discrete Math. 13 (1975), 399–407.

2010 Mathematics Subject Classification: Primary 11B13, Secondary 11A07, 03G15, 11-04, 11U10, 11Y55. Keywords: Ramsey algebra, relation algebra, finite field, sum-free set, sumset.

(Concerned with sequence \underline{A263308}.)

Received September 11 2016; revised version received August 29 2017. Published in Journal of Integer Sequences, August 31 2017.

Return to Journal of Integer Sequences home page.