August | 2022 | grpaseman's Blog

I am looking for work. Towards that end I thought I would add some new number theory to this blog to show some of my creative efforts.

This post is more expository than rigorous. It is an attempt to strategize and explain: the rigor is left for a different article.

A problem asks when a certain sum of binomial coefficients is a power of 2. We look for interesting triples of positive integers $(m,r,k)$ such that $\sum_{i=0}^r {m \choose i} = 2^k$ ; uninteresting triples have $r =0,1,m,$ or $r=\frac{m-1}{2}$ . (Familiarity with binomial coefficients will help the reader: check out the introduction to binomial coefficients on Wikipedia ; one important fact is ${m \choose r}$ is a multiple of prime $p$ when $m-r \le p \le m$ and $0 < 2r < m$ .)

This problem of finding interesting $(m,r,k)$ has appeared in the literature in some other forms (see here ; hat-tip to Brian Hopkins). At this writing this problem is still unsolved (there are only two known interesting triples and not much known beyond that); what new idea can be brought to bear on this?

New Idea: use divisibility relations (which Mersenne numbers are multiples of which primes) to limit the search space of possibilities. (Mersenne numbers have the form $2^a - 1$ for positive integer $a$ : because we are dealing with odd primes $p$ , $2^a - 1$ is a multiple of $p$ if and only if $2^{a+b} - 2^b$ is a multiple of $p$ , where $b$ is a nonegative integer; in this article, Mersenne numbers will hide in expressions like $2^{a+b} - 2^b$ .)

In particular, suppose we have an interesting solution $(m,r,k)$ of our problem. Then $1<r<\frac{m-1}{2}$ , and for expository purposes $k$ “is like” $r\log m$ , where I am using a base 2 logarithm. ( $k$ is closer to $r\log m - \log r!$ , but we are feeling our way: if $k$ does not exist, precision won’t matter.) Let’s look at odd primes $p$ which are less than but close to $m$ . We ask that $m-r \le p \le m$ and will write this as $p \in [m-r,m]$ . Other uses of notation like $\mid$ will be explained soon after they are used.

Observation A (read Exercise for the reader): Suppose $(m,r,k)$ is an interesting solution; for any prime $p \in [m-r,m]$ it follows that $p \mid 2^{m-1} - 2^k$ (i.e. $2^{m-1} - 2^k$ is a multiple of $p$ ).

Hint: One can write $2^{m-1} - 2^k$ as a sum of multiples of $p$ , where most of these multiples are binomial coefficients. The exercise is to consider when $m$ is even and when $m$ is odd, and find the right way to write the sum for each case.

What can we do with this? First let us introduce $ord(p)=j$ , the smallest integer $j$ such that $p \mid 2^j - 1$ . This is also called the multiplicative order of $2 \bmod p$ , and can be defined for factors $d$ other than $p$ as well as for bases other than 2. For this post we always use base 2 and the notation $ord(p)$ .

We will also use notation for “is a multiple of” , or “evenly divides”. $a \equiv b \bmod p$ means $a-b$ is a multiple of $p$ . Sometimes we say $a$ equals $b \bmod p$ to mean the same thing. Another way uses the symbol $\mid$ to read “evenly divides” so $p \mid (a-b)$ and variations are used. I use $lcm$ and $gcd$ for least common multiple and greatest common divisor, respectively, of two integers.

Most of the time the signs $p$ and $q$ will stand for odd primes, and if I use an expression that might not be an integer (e.g. $\log 127$ ), I round it to a nearby integer when needed. (Again, the goal is comprehension over rigor; a rigorous version will be made available.)

Observation A (combined with elementary considerations on multiplicative order) says that $m-1-k$ is a multiple of $ord(p)$ . This gives a constraint on $k$ , a weak form of this being $m-1 - k \ge ord(p)$ .

Now $ord(p) \le p-1$ . If $ord(p) = p-1$ then $m- p \ge k$ , and so $r \ge k$ . But wait! $k$ is like $r\log m$ , which means $\log m$ is like 1. Let’s take a closer look.

$2^k$ is bigger than the biggest term in the sum which is ${m \choose r}$ , so we have $k > r\log (m-r) - \log (r!) > r[\log (m-r) - \log (r/2)] > r$ (remember $\log$ is base 2). So we get $r > r$ ?!?

Clearly we did something wrong, and that something is assuming that such primes $p$ with such large orders lie in $[m-r,m]$ . So our solutions $(m,r,k)$ must avoid these $p$ with large orders.

Some of these primes have smaller orders, like $\frac{p-1}{2}$ or $\frac{p-1}{3}$ , or even smaller. What if $p$ is like this?

The consequence above ( $ord(p)|m-1-k$ ) gives an upper bound on $k$ of $k < (m-1)$ minus some multiple of $ord(p)$ , with no obvious contradiction. However, if we have two distinct primes $p, q \in [m-r,m]$ we can improve upon this.

Indeed, Observation A says $ord(p)$ and $ord(q)$ both divide $m-1-k$ . This means $z= lcm(ord(p),ord(q))$ also divides $m-1-k$ , unless $z> m-1 -k$ , in which case $z$ is too big. So $[m-r,m]$ better not contain two such primes $p$ and $q$ with big $z$ not dividing $m-1-k$ . These are two ways to use Observation A.

A quick computer search reveals about ten pairs of consecutive primes below 3000000 which obey $z < m$ . So except for these ten pairs and maybe larger pairs, our interval $[m-r,m]$ must avoid containing two or more primes.

This is quite a restriction, and suggests (in an asymptotic sense I won’t explain here) $r$ must have a size close to $\log m$ . Of course, our knowledge of prime gaps is not strong enough to support this (indeed, there may still be a large $m$ where $[m- \sqrt{m},m]$ contains no primes at all, and so $r$ might also be as large), but Observation A does suggest using $ord(p)$ to improve a computer search: Given $m$ , increase $r$ until $m-r$ reaches such a prime or pair of primes. However, there is more.

Observation B (second Exercise): Let $p > r$ , and suppose there is a multiple of $p$ in $[m-r,m]$ , say $p$ divides $m-j$ . Then $p$ divides $2^k - 2^j$ .

Hint: The binomial coefficients ${m \choose 0}$ through to ${m \choose j}$ sum up to something equal to $2^j \bmod p$ . Check that the rest (up to ${m \choose r}$ ) are multiples of $p$ .

How do we use this? If we have a composite (meaning, not prime) number $m-j \in [m-r,m]$ with a large prime factor $p$ , then $k -j$ is a multiple of $ord(p)$ , so $r\log(m) > ord(p)$ , so (roughly speaking) $r$ must be about $ord(p)/\log(m)$ or bigger. We need to have $r < p$ for this to work as $m \choose p$ may not be a multiple of $p$ .

So we now have a plan for a computer search: Start with $m$ , and find a prime factor $p$ of $m$ with the largest order $ord(p)$ . If $ord(p)$ is much greater than $\log m$ , then we have a useful lower bound on $k$ . Now we look for $q$ a prime factor of $m-1$ (or later of $m-j$ ) with a larger order, meanwhile checking the sum to make sure we have not hit a power of 2. If we get to $j$ such that $m-j$ is prime and $ord(m-j)=(m-j-1)$ , we stop, for we know that such $m-j$ blocks $(m,r)$ from being part of a solution.

This suggests starting with $m$ that have only prime factors with very small orders (and one of the interesting $(m,r,k)$ is $(90,2,12)$ ). Even then, if we have two such prime factors $p$ and $q$ dividing $m-j$ , the $lcm$ of the orders must divide $k-j$ ; in some cases this means that $r$ is no smaller than the minimum of $q$ and $p$ . A similar condition applies for $p \mid m-j$ and $q \mid m-i$ .

We can do more with observation B. Suppose we are testing $m$ and $r$ and assume they can be a solution. Suppose there are adjacent numbers $n$ and $n+1 \in [m-r,m]$ , and further suppose $p \mid n$ and $q \mid n+1$ , with $ord(p)$ and $ord(q)$ both even. If $m, r$ is a tentative solution, and $p$ and $q$ are both greater than $r$ , then there is an $i$ with $m-i=n$ and positive integers $a$ and $b$ so that $k = ord(p)a + i = ord(q)b + i +1$ , giving that $k$ is both even and odd. This is a contradiction, and one way out is that $r$ is at least as big as the minimum of $p$ and $q$ .

More generally, if $n,n+d \in [m-r,m]$ and $p \mid n$ and $q \mid n+d$ , and $gcd(ord(p),ord(q))$ does not divide $d$ , then $r$ can be no smaller than the smaller of $q$ and $p$ . This is useful when there are upper bounds on $r$ that can lead to a contradiction.

These observations and their ramifications suggest that one can implement a relatively quick computer search for solutions, with the likely outcome that the only new solutions will be trivial.

We don’t have a proof yet that $r$ is either less than $\sqrt{m}$ or else $r$ is at least $\lfloor m/2 \rfloor$ , but the search should confirm that is true for all solutions $(m,r)$ , given that $m-r$ has to be “within a few primes” from $m$ .

There is an extension of Observation A: if $p = q^a$ , that is if one replaces $p$ prime by a prime power, then $q \mid 2^{m-1} - 2^k$ . A similar extension of Observation B is being tested, and may imply conditions forcing $r$ to be greater than a prime power $p$ dividing a number in $[m-r,m]$ .

I will report later on further developments. The plan now is to try various combinations of conditions to see which combinations are most efficient in terms of comprehension and computability, and do a quick search for all tentative solutions with $m < 10^{12}$ and further. I will also try pushing on the theory some more. (If things go well, I will form a collaboration to help with this.)

	On A Theorem Of Sylv… on Here is a lovely generalized c…
	Here is a lovely gen… on Some nice combinatorics for yo…
	grpaseman on Time for a Change
	Yaakov Baruch on Time for a Change
	grpaseman on Happy Anniversary To Me!

grpaseman's Blog

philosophy of systems and design

Month: August 2022

Building a Mathematical Portfolio: Combinatorial Number Theory