Month: March 2024

On A Theorem Of Sylvester And Schur

Posted by

0

Here is my Pi Day post (a filled out sketch of more combinatorial number theory), where \pi(x) represents the prime counting function. After the S and S content I have some updates.

I found an iterative argument that gives a new (to me) proof of (a weak form of) an old result: For all integers n \geq k \geq 1, the product (n+1)\cdots(n+k)= k! {{n+k} \choose k} has a prime factor bigger than k.  The argument uses combinatorial tools, and extends an argument used by P. Erdös  and J. J. Sylvester.  Here is my rendition of their argument:

Suppose (n+1)\cdots(n+k) has no large prime factors.  By extending Sylvester’s Law of Ademption, I can write {{n+k} \choose k} as a product of prime powers p^{\alpha_p}, where p \leq k are prime, \alpha_p \geq 0 are integer exponents depending on p, and most importantly \prod_{p \leq k} p^{\alpha_p} \leq \prod_{p_i \in [1,k]}(n+k+1-i).  (The Law of Ademption says p^{\alpha_p} \mid {{n+k} \choose k} implies p^{\alpha_p} \leq n+k; the extension uses distinctness of prime powers to get the product upper bound.)  For k\geq 8,

(n+1)\cdots(n+k) = k! \left(\prod_{p \textrm{ from } [1,k]} p^{\alpha_p}\right) \leq k! \left(\prod_{p_i \in [1,k]} (n+k+1-i)\right)

giving  n^{k-\lfloor k/2 \rfloor} < \prod_{i=1}^{k -\lfloor k/2 \rfloor} (n+i) \leq \prod_{i=1}^{k-\pi(k)} (n+i) \leq k! < (k^2)^{k -\lfloor k/2 \rfloor} .

This uses that \pi(k), the count of primes coming from [1,k], is \leq \lfloor k/2 \rfloor for k \notin \{3,5,7\} (and real k\geq 8); the \leq between the two \prod in the second display makes the full inequality weaker.

Taking roots gives n < k^2, which gives a weak form of the contrapositive: for all integers n \geq k \geq 8, if (n+1)\cdots(n+k) has no prime factor bigger than k, then n <k^2.  I extend this to give n <4k for k\geq 8, and then hint at how to get n<2k for k \geq 50.

The easy cases are k>64, so imagine big k in the argument below.  Again assume (n+1)\cdots(n+k) has no prime factors > k, use the extended Law and \pi(k)\leq \lfloor k/2 \rfloor to get 

(*) (n+1)\cdots(n+k- \lfloor k/2 \rfloor) \leq k! .

Set m=k -\lfloor k/2 \rfloor. We seek distinct positive integers a_i with \prod_{i=1}^m (n+i) \leq k! \leq \prod_{i=1}^m a_i, which will give us n+m < \max(a_1,\ldots,a_m).  Break k! into m factors b_i (possibly nondistinct).  When k is even, m=k/2: write k!= \prod_{i=1}^m (k+1-i)i.  When k is odd, k-1=2m-2: now write k! = k (k-1)! = k \prod_{i=1}^{m-1}(k-i)i.  So b_i = one of (k+1-i)i or (k-i)i, depending on the parity of k (with b_m=k when k is odd). Then \max(b_i)=m(m+1) if k is even, and \max(b_i)=m(m-1) if k>3 is odd.

If the b_i were a sequence of consecutive integers,  n+m \leq \max(b_i) might happen.  However, m>3 and all but at most one of the b_i are even, so we get n+m < m(m \pm 1), which implies n+k < (m+1)^2: this powers the iteration.  The b_i are distinct, so let a_i=b_i; enough b_i are even, so for k \geq 8 we have n+k < (k/2 +1)^2.

Now for any prime p \geq m+1, p^2 > n+k: Sylvester’s Law says p^2 does not divide {{n+k} \choose k}.  Recalling that p runs over primes \in [1,k],

(**) (n+1)\cdots(n+k) = k! \left(\prod_{p \leq m} p^{\alpha_p}\right) Q

where Q= \prod_{p>m} p^{\epsilon_p} means p \in [m+1,k] and \epsilon_p \in \{0,1\}.  Now Q \mid \prod_{p >m} p which divides {2m-1 \choose m-1} < 4^{m-1}.  This yields a new inequality like (*), using m\geq 8 (so that \pi(m)\leq \lfloor m/2 \rfloor and k \geq 15):

(n+1)\cdots(n+k-\lfloor m/2 \rfloor) \leq k! Q < k! 4^{m-1} \leq k! 4^{k-m}

This has more terms n+i on the left hand side than does (*).  We want k- \lfloor m/2 \rfloor many distinct positive integers a_i so that k! 4^{m-1} < \prod_{i=1}^{k - \lfloor m/2 \rfloor} a_i.  We can then conclude n + k -\lfloor m/2 \rfloor < \max{a_i}, where now < comes from using a weak upper bound 4^{m-1} on the product \prod p^{\epsilon_p} (a_i could be consecutive, but we don’t lose <).

So for k odd, write k!4^{m-1} = \left(\prod_{j=m+1}^k 4j \right) m!; for k even there is more room: write k!4^m = \left(\prod_{j=m+1}^k 4j \right) m!.  k-m of our terms have the form b_i =4(k+1-i), and the remaining m - \lfloor m/2 \rfloor terms come from writing m! as we did for k! above. Note for small k, \max(b_i) = 4k could happen.

Now suppose the b_i are distinct. (When they aren’t, we will fix it.) Then  n+k - \lfloor m/2 \rfloor< \max(b_i), and proceed depending on b=\max(b_i):

If b > 4k, the largest term looks like (m/2 \pm 1)m/2 , and in both cases n+k < m/2 + m/2(m/2+1) < (m/2+1)^2.  Now p\geq m/2 +1 implies p^2 does not divide {{n+k} \choose k}.  As with (**), iterate by enlarging Q and reducing the number of p with possibly large \alpha_p by about half.  Since k is large,  m/2 \geq 8 and so \pi(m/2) \leq \lfloor m/4 \rfloor. (m/2 < 8 is dealt with later.)  The product of primes in [m/2 +1, m] are bounded above by 4^{m/2-1}, and now we write

(n+1)\cdots(n+k - \lfloor m/4 \rfloor) < k! 4^{k- \lceil m/2 \rceil} .

Iterating this gives inequalities like 

(n+1)\cdots(n+k - \lfloor m/(2^{r+1})\rfloor) < k! 4^{k - \lceil m/(2^r) \rceil }

until we get to r with (m/(2^r))(m/2^r \pm 1) =b \leq 4k.

If b \leq 4k and the terms are distinct,  (n+k - \lfloor m/2^r \rfloor) \leq 4k which means n+k < 4.4 k (since k \geq 15 so we did the iteration, so r>0) and we get n < 3.4k. 

Now I handle the issue of distinctness.  The b_i are usually not distinct: at least one of the terms making up m! often is a multiple of 4 \in [4m+4, 4k].  The fix is easy: if the largest term (m/2\pm 1)m/2 is different from 4k, add one to all the terms (m-i)i or (m+1-i)i which duplicate a multiple of 4 from [4m+4,4k], and set these new terms (which are odd \in [4m+5,4k-3]) to a_j for appropriate j; otherwise let a_j=b_j.  Now all the a_i are distinct, their maximum is b, and their product is larger than the product of the b_i, so the inequality and conclusion n<3.4k are maintained.

The final case is b =4k.  One can go two ways: add one to all the duplicates as before and get \max(a_i)=1+b, which is a minor loss but for large k we still end up with n<3.4k, or tweak b and one other even term t< 4m+4, e.g. t=2(m-2): replace (b,t) (which equals (4k,t)) by (b-1,t+1).  We get distinctness, preserve the maximum, and the bound n < 3.4k prevails.  This works for all m/2 \geq 8 by the argument above, and special handing of m/2 < 8 permits the same conclusion. (The main challenge is to write 7! as (7*2)(6*3)(5*4), which is needed only for k<15.)

There are variations on this which get better results.  The initial stage of rewriting k! into the product of distinct b_i can be transformed: given b_i, compute a_i such that a_i are almost consecutive and sum a_i is slightly bigger than sum b_i (which looks like twice the sum of squares from 1 up to m^2, minus an odd term).  This results in a maximum of about 2b/3 +m/2, and can be used to handle small k.

One can also do this to \prod_{i=m+1}^k 4i, replacing it with a near-consecutive sequence with maximum term near 2(k+m+1) + (k-m)/2.  One then sees that after the second iteration, one can compare b_i to 3k and continue the iteration, so for k>192=3*64 one easily gets n<2k and one approaches n< (1.5+ \epsilon)k for large k.  One can combine these techniques and others to get further improvements.  Currently I see n<2k for k \geq 50, and I am writing up variations to get n<2k for k\geq 1.

The main feature of this argument is that it is composed of arithmetic and combinatorial arguments: all we use about primes are that most of them are odd, and that 1 and 9 are not prime.  No tools from analysis, just the Law of Ademption, the bound \prod p < 4^{m-1}, the Fundamental Theorem of Arithmetic, some other basic arithmetic, and the stamina to follow the iteration and explore options.  Alan Woods explored using similar methods with a form of discrete logarithm to prove the Sylvester-Schur theorem in a weak fragment of arithmetic: it is worth investigating how far this method of finding distinct a_i can be stretched to show the result n\leq k.

It has been a personal challenge to distill this sketch down to these few pages.  I invite you to find further simplifications which are as combinatorial in nature.  When I have a suitable preprint written, I will include it in a future post: those eager to see a rough draft can be a reviewer and request a PDF through email.

For contrast, consider the literature:  I find the proof of Erdös the easiest to follow, but still wanting since he leaves many cases to check.

Bibliography (links available in PDF draft):

Sylvester, James Joseph. “On arithmetical series.” Messenger of Math 21. (1892): 1-19.  (The same issue has his generalization to primitive arithmetic progressions in later pages.)

Schur, I., Einige Satze uber Primzahlen mit Wendung auf Irreduzibilitatsfragen, Sitzungberichte der preussichen Akademie der Wissenschaften, Phys. Math. Klasse, 23 (1929), 1–24. (He uses analytic methods a la Chebyshev.)

Erdös, P. (1934). A theorem of Sylvester and Schur. Journal of the London Mathematical Society, 1(4), 282-288.

Faulkner, M. (1966). On a theorem of Sylvester and Schur. Journal of the London Mathematical Society, 1(1), 107-110. (Shows the large prime $\geq 7k/5$.)

Hanson, D. (1973). On a theorem of Sylvester and Schur. Canadian Mathematical Bulletin, 16(2), 195-199.  (Uses tighter estimates on $\prod p$.)

Woods, A. (1981). Some problems in logic and number theory and their connections. Ph. D. Thesis, Univ. of Manchester.

Saradha, N., & Shorey, T. N. (2003). Almost squares and factorisations in consecutive integers. Compositio Mathematica, 138(1), 113-124.

Granville, A. (2020). Number theory revealed: a masterclass (Vol. 127). American Mathematical Society.  (See Appendix 5A.)

Updates: Our second paper (with Stephen Glasby) has been accepted for publication: when formalities have been concluded I will point to the journal. The ArXiv version is at https://arxiv.org/abs/2310.12517 for those who can’t wait. We apply the lovely generalized continued fraction I mentioned in 2022 (https://grpaseman.wordpress.com/2022/02/22/here-is-a-lovely-generalized-continued-fraction/).

The preannouncing of SCS 2023 was premature: I apologize to all who were anticipating it. I intend to have announcement out for SCS 2024 in a few weeks.