Rado’s Theorem : Rado and the Regularity of Systems of Linear

Rado’s Theorem : Rado and the Regularity of Systems of Linear

Science

This paper presents an overview of Rado’s Theorem and advances in proving Rado’s Boundedness Conjecture. We discuss a proof of Rado’s Theorem and then present Rado’s Boundedness Conjecture, as well as several reductions of the conjecture. Lastly, we present several cases of Rado’s Boundedness Conjecture that have been proved. 

Introduction 

Can we find order in disorder? This has been the fundamental question of Ramsey Theory, a branch of combinatorics that studies the conditions under which order must appear. In 1916, Isaai Schur proved arguably the first result in Ramsey Theory [FK06] involving the arbitrary colorings of the natural numbers and monochromatic solutions to systems of equations. 

Theorem 1. Schur’s Theorem (Schur 1912 [Sch12]). For every positive integer r, there is a least positive integer, S(r), such that for every r-coloring of the positive integers from 1 to S(r), there is a monochromatic solution to x + y = z. 

Consider a brief example of Schur’s theorem for r = 2. If we consider the coloring of the positive integers {1, 2, 3, 4}, we can devise a coloring such that there is no monochromatic solution to x+y = z. Take, for example, {1, 2, 3, 4}. Any other partitioning of these values leads to a monochromatic solution. However, if we consider the coloring of {1, 2, 3, 4, 5} we have a monochromatic solution regardless of what color we choose for 5. For example, 2 + 3 = 5 or 1 + 4 = 5. Thus, S(2) = 5. 

Schur’s Theorem represents one approach to answering the fundamental question of Ramsey Theory. Schur’s Theorem is an attempt to find the conditions under which there exist monochromatic solutions to systems of equations (order) under arbitrary colorings of the natural numbers (disorder). 

In 1927, B.L. van der Waerdan proved another important result in Ramsey Theory [FK06] that expanded upon the study of monochromatic systems of equations. Theorem 2. Van der Waerden Theorem (van der Waerden 1927 [vdW27]). For all positive integers k and r, there is a least positive integer W(k, r), such that for every r-coloring of the positive integers from 1 to W(k, r), there is a monochromatic k-term arithmetic progression.

The works of Schur and Van der Waerdan inspired Richard Rado, who was able to generalize these theorems in his 1933 thesis. Rado observed that the results of Schur and Van der Waerdan both involved systems of equations. Rado introduced the concept of regularity to describe systems of linear equations with monochromatic solutions under arbitrary colorings. Specifically, let Ax =b be a finite system of linear equations, where all the entries of A and b are integers. Rado defined what it meant for a finite system of linear equations to be r-regular and regular. 

Definition 1.1. r-Regular [FK06]. A finite system of linear equations, Ax = b, is r-regular if for every r-coloring of N = {1, 2, …}, there is a monochromatic solution to Ax = b. 

Definition 1.2. Regular [FK06]. (Also known as regular ). A finite system of linear equation Ax = b is regular if it is r-regular for all positive integers r. 

Theorem 3. Rado’s Theorem. (Leader 2000 [Lea19]) A rational matrix, A, is regular if and only if A has the columns property. 

After introducing and proving Rado’s Theorem, Rado generalized further. He proposed what is known as Rado’s Conjecture. 

Conjecture 4. Rado’s Conjecture. (Fox and Kleitman 2005 [FK06]) For all positive integers m and n, there exists a positive integer k(m, n) such that if a system of m linear equations in n variables is k(m, n) regular, then the system is regular. 

Although Rado’s Conjecture has not been proved, recent progress has been made to reduce the conjecture to the case of one homogeneous linear equation and to prove specific cases of the conjecture. This paper discusses Rado’s Theorem and its proof in detail. It introduces Rado’s Conjecture and a reduction of the Conjecture to homogeneous equations, proposed by Fox and Kleitman. Lastly it discusses more recent developments in proving Rado’s Conjecture. 

Rado’s Theorem 

In this section, we will present and prove a version of Rado’s Theorem. Rado’s Theorem is re-introduced below. 

Theorem 5. Rado’s Theorem. (Leader 2000 [Lea19]) A rational matrix, A, is regular if and only if A has the columns property. 

One important consequence of Rado’s Theorem is that it shows that regularity can be checked in finite time. One does not have to naively consider the arbitrary colorings of the natural numbers for arbitrarily large numbers of colors in order to show that a system of equations is regular. Furthermore, one must only check to see if the system of equations satisfies the columns property. 

We can first consider the case of one equation. Let us have a matrix (a₁, a₂, …,a_n). 

Lemma 6. A = (a₁, a₂, …, a_n) has the columns property if and only if we have one of the two cases: _1. P_i∈Ia_i = 0 where all a_i 6= 0 for some non-empty I ∈ [n] 

2. a₁ = a₂ = … = a_n = 0 

Proof. ( =⇒ ) Assume A has the columns property. Then, there exists some nonempty partition B_{1 such that} P_i∈B1a_i = 0. There exist 3 possibilities for the entries in B₁. 

1. Case 1. All entries in B₁ are 0. Consider the following subcases 

(a) Subcase 1. All entries in A are 0. This is case (2) of the theorem. 

(b) Subcase 2. Some entries in A are not 0. Assume, for the sake of contradiction, that _{there does not exist some I with nonzero values where} P_i∈Ia_i = 0. Then we could iterate through the partitions of A, and we could find the first partition B_i that contained _{nonzero values. By assumption,} P_i∈Bia_{i 6= 0. Then} P_i∈Bia_i could not be spanned by any zero vectors in the previous partitions B_j where j < i, thus violating the columns property. Therefore, we must have that there exists some non empty I of nonzero values _where Pi∈Is = 0, satisfying case (1). 

2. Case 2. Some, but not all, entries in B₁ are 0. Remove the nonzero entries from B₁ and add them to a new partition, B⁰₁. Now I = B⁰₁. 

3. Case 3. All entries in B₁ are nonzero. Let I = B₁. 

( ⇐= ) Assume that A satisfies the columns property. We have two cases. 

_{1. Case 1.} P_i∈Ia_i = 0 where all a_i 6= 0 for some non-empty I ∈ [n]. Then A satisfies the columns property with B₁ = I as B₁ spans the entire space. 

2. Case 2. a₁ = a₂ = … = a_n = 0. Let B₁ be all of the columns in A. We are done. 

In order to prove Rado’s Theorem for the case one equation, We will only need to focus on the case where A consists of all entries that are nonzero. Other cases are either trivial or can be reduced to the case of nonzero entries. 

1. Case 1. If A = (0, 0, …, 0), then by Lemma 6, A has the columns property. A is also regular because any x is a solution to Ax = 0. 

2. Case 2. If A contains some, but not all 0 entries, we can focus on the submatrix A⁰ of A that consists of only nonzero entries. The zero entries of A will not affect regularity or whether A has the columns property. 

By the argument above and by lemma 6, in order to prove Rado’s Theorem for one linear equation with nonzero coefficients, it is sufficient to prove the following. 

Theorem 7. Rado’s Little Theorem. Let A be a 1 × n matrix with nonzero entries. A is regular if _{and only if there exists some nonempty subset I of nonzero values in A where} Pi∈Is = 0. 

We will prove this theorem by proving both directions of the theorem individually. We will first show the forward direction of Rado’s Little Theorem. 

Proposition 8. [Lea19] If a matrix A = (a₁, …, a_n) of nonzero entries is regular, then there exists _{some nonempty subset I of nonzero values in A such that} Pi∈Is = 0 

Proof. Let x ∈ N and consider a base p expansion of x, i.e., x = d_rp^r + d_r−1p^r−1 + … + d₁p¹ + d₀. Let L^p(x) represent the lowest value of r such that d_r 6= 0 in the base p expansion of x. Let d^p(x) be the value of d_L^p_(x), the smallest nonzero digit in the base p expansion of x. For example, consider p = 3 and x = 15. The base 3 expansion of 15 is 15 = 1(3)² + 2(3) + 0. Thus L³(15) = 1 and d³(15) = 2. 

_{Fix p such that p >} Pⁿ_i=1 a_i. Define dp-coloring, a coloring c, on all x ∈ N such that c(x) = d^p(x). Since A is regular, there exists a monochromatic solution to Ax = 0 where all x_i ∈ x have the same color. Let this color be d, i.e., c(x_i) = d^p(x_i) = d. 

Let L be the lowest value of L^p(x_i) for all x_i ∈ x. 

L = min {L^p(x_i)|1 ≤ i ≤ n} 

Now define a dp-partition of all x_i ∈ x. Let I be the set of index values corresponding to the x_i where L^p(x_i) = L. 

I = {i|L(x_i) = L} 

For example, consider a solution in base 7 expansion: x = [125000, 1350, 500, 11150]. By the coloring defined above, each x_i has the color 5. In this example, we have that L = 1 and that I = {2, 4}. 

Now consider the base p expansion of Ax = 0. 

_{Ax =}Xⁿ i=1 

a_ix_i = d_rp^r + d_r−1p^r−1 + … + d₁p + d₀ = 0 

By the definition of L, d_i = 0 if i < L and d_L = d. 

a_ix_i = d_rp^r + d_r−1p^r−1 + … + d_L−1p^L−1 + dp^L = 0 

Divide by dp^L. 

_{Ax =}Xⁿ i=1 

Xⁿ i=1 

a_ix_i 

dp^L₌d^r_dp^r−L ₊d_r−1 

_dp^r−1−L _{+ … +}d_L+1 

_dp + 1 = 0 

Convert to modulo p and expand the summation. 

_{Ax =}Xⁿ i=1 

dp^L₌X 

a_ix_i 

i∈I 

dp^L₊X 

a_ix_i 

i6∈I 

a_ix_i 

dp^L≡ 0 mod p 

When i 6∈ I, x_i has a 0 in the Lth place in its base p expansion. Thus, dividing x_i by p^L yields 0 in modulo p. When i ∈ I, x_i has d in the Lth place in its base p expansion. Dividing x_i by p^L yields 

d in modulo p. 

_{Ax =}X i∈I 

dp^L₌X 

a_id 

i∈I 

p^L_≡X 

a_i 

i∈I 

a_i ≡ 0(modp) 

_{We chose p to be large enough that p >} Pⁿ_i=1 a_i. Thus, 

X i∈I 

a_i = 0 
Therefore, there exists a nonempty set I where the sum of the entries in I are 0. We are done.

Before we prove the other direction of Rado’s Little Theorem, let us first consider the following lemma. 

Lemma 9. (Leader 2000 [Lea19]) Let λ ∈ Q. Then whenever N = {1, 2, …} is finitely colored, there exist monochromatic x, y, and z with x + λy = z. 

Proof. Consider three cases for λ. 

1. Case 1: λ = 0. We are left to find a monochromatic solution to x = z which exists for all finite colorings of N. We are done. 

2. Case 2: λ < 0. This case can be reduced to the case of λ > 0. Rewrite the equation as z − λy = x where λ > 0. 

3. Case 3: λ > 0. Let λ =^r_s where r, s ∈ N. Proof of this case is below. 

Let k be the number of colors used in an arbitrary coloring of N. It remains to show that whenever [n] is k-colored, there exist monochromatic x, y, and z such that x + ( ^r_s)y = z. We shall prove this with induction on k. 

Base Case. k = 1. Let n = max (s, r + 1). There exists a monochromatic solution with (x, y, z) = (1, s, r + 1). 

Inductive Step. k > 1. Assume that the lemma holds for (k − 1) colors and that n is suitable for (k − 1). That is, for any arbitrary (k − 1) coloring of [n], there exist monochromatic x, y, z that are solutions to x + ( ^r_s)y = z. Recall Van der Waerdan’s theorem, which states that there exists a value W(k, n) such that for all k-colorings of {1, 2, …, W(k, n)}, there exists a monochromatic arithmetic progression of length n. Consider the k-coloring of [W(k, nr + 1)]. By Van der Waerdan’s theorem, there exists a monochromatic progression of length (nr + 1). Let the progression have color c and be of the form: a, a + d, a + 2d, …, a + nrd. Consider the following set B = {ds, 2ds, …, nds}. There are two cases. 

61. There exists ids ∈ B with color c. Then we have that (x, y, z) = (a, ids, a + idr) are a set of monochromatic solutions to x + ( ^r_s)y = z. 2. There does not exist ids ∈ B with color c. Then the set B is (k−1)-colored. Since |B| = n, by the inductive hypothesis, there exist monochromatic x, y, z ∈ B that are solutions to x + ( ^r_s)y = z.

Now consider the proof of the other direction of Rado’s Little Theorem. 

Proposition 10. [Lea19] If for a given matrix A = (a₁, a₂, …, a_n) of nonzero entries, there exists _{some nonempty subset I of the entries in A such that} Pi∈Is = 0, then A is regular. 

Proof. We will consider an arbitrary coloring of N = {1, 2, …} and find some x such that x is a solution to Ax = 0 and x is monochromatic. Fix some i_o ∈ I. There exist an infinite set of solutions for Ax = 0. Therefore, we can find a solution x that satisfies the following for all x_i ∈ x. 

_{x +(}P_i6∈Ia_i) 

a_i0y = z 

By Lemma 9, for any arbitrary coloring of N, there exists a monochromatic solution to x + λy = z where λ ∈ Q. Thus, taking λ =⁽P_i6∈Ia_i) 

A is regular. 

aⁱ₀, there exists a monochromatic x, y, z such that Ax = 0. Thus, 

combining proposition 8 and proposition 10, we have proved Rado’s Theorem for the case of one linear equation. 

The proof of the general case of Rado’s Theorem is rather long but it follows a similar structure to the proof of Little Rado’s Theorem. To prove the forward direction of the theorem, we construct a dp-coloring of the natural numbers. We express Ax = 0 as column-wise multiplication: x₁c⁽¹⁾ + 

x₂c⁽²⁾ + … + x_nc⁽ⁿ⁾ = 0. We partition columns based on their corresponding x_i value, specifically what place the d digit is located in the base p expansion of x_i. By partitioning columns in this way, we can show that A has the columns property. To prove the other direction of Rado’s Theorem, we must expand on Lemma 9 so that it accounts for a specific set of linear equations called (m, p, c)-sets. We prove that there always exists a monochromatic (m, p, c)-set for all colorings that is a solution to Ax = 0 if A satisfies the columns property. For a definition of (m, p, c)-sets and a formal proof of Rado’s Theorem, see [Lea19]. 

Rado’s Boundedness Conjecture 

In 1933, after proposing and proving the connection between regularity and the columns property of matrices, Rado introduced a conjecture regarding the regularity of systems of equations. Rado conjectured that one could show whether a system of equations was regular without any knowledge of the coefficients in the equations. 

Conjecture 11. Rado’s Boundedness Conjecture. (Fox and Kleitman 2005 [FK06]) For all positive integers m, n, there exists a positive integer k(m, n) such that if a system of linear equations with m equations and n variables is k(m, n)-regular, then it is regular. 

Rado’s Conjecture has not been proved. However, advancements have been made towards reducing the conjecture to simpler cases. Specifically we have the following two reductions. 

Reduction 1. Rado’s Boundedness Conjecture is true if it is true for the case of one equation (m = 1). (Rado 1933 [Rad33]) 

Reduction 2. Rado’s Boundedness Conjecture is true if it is true for homogeneous equations, i.e, a₁x₁ + a₂x₂ + … + a_nx_n = 0. (Fox and Kleitman 2005 [FK06]) 

Reduction 2 has been proved recently by Fox and Kleitman. In order to prove the reduction, we must first consider the following lemma. 

Lemma 12. Straus’s Lemma (General Case) (Straus 1975 [Str75]) . Let A be an abelian, additive group and let b ∈ A^∗, where A^∗consists of the nonzero entries of A. For 1 ≤ i ≤ n−1, define (n−1) functions, f_i: A → A. Define r to be the following. Here, ord(b) refers to the order of b in A. 

where c(x_i) = c(y_i). Proof. We will show that there is a coloring of A such that there is no monochromatic solution. Let A be the result of a homomorphism that sends A to [0, 1) and sends b to b such that

Fox and Kleitman reduces the proof of Rado’s Boundedness Conjecture to the case one homogeneous
linear equation. In the following section we will explore recent developmentss in proving the reduced
version of Rado’s Boundedness Conjecture.

Proved Cases of Rado’s Boundedness Conjecture

Conclusion

Written by Talia Pelts

Science

Rado’s Theorem : Rado and the Regularity of Systems of Linear

References 

[FK06] Jacob Fox and Daniel J. Kleitman. On rados boundedness conjecture. Journal of Combi natorial Theory, Series A, 113(1):84–100, 2006. 

[Lea19] I.B. Leader. Ramsey theory, 2019. 

[Rad33] R. Rado. Studien zur kombinatorik. 36:242–280, 1933. 

_{[Sch12] Issai Schur. Uber die existenz unendlich vieler primzahlen in einigen speziellen arithmetis-} ¨ chen progressionen. Sitzungsberichte der Berliner Math, 1912. 

[Str75] E.G. Straus. A combinatorial theorem in group theory. 29(129):303–309, 1975. [vdW27] B.L. van der Waerdan. Beweis einer baudetschen vermutung. Nieuw. Arch. Wisk., 15:212– 216, 1927.

Rado’s Theorem : Rado and the Regularity of Systems of Linear