The Waring conjecture – actually a problem associated with a number of conjectures, many now being solved – is one of the most fascinating mathematical problems. This article covers new aspects of this problem, with a generalization and new conjectures, some with a tentative solution, and a new framework to tackle the problem. Yet it is written in simple English and accessible to the layman.
I also review a number of famous related mathematical conjectures, including one with a $1 million award still waiting for a solution, as well as Goldbach’s conjecture, yet unproved as of today. Many curious properties of the Floor function are also listed, and the emphasis is on machine learning and efficient computer-intensive algorithms to try to find surprising results, which then need to be formally proved or disproved.
1. General Framework
The Waring problem deals with the representation of positive integers by sums of k-th powers of positive integers. The smallest number of terms required to cover all integers, is denoted, for a given k, as g(k). For instance, it has been known for a long time that any positive integer is the sum of four squares. However, the number 7 can not be expressed as the sum of three squares, thus g(2) = 4.
Let us introduce some useful notation. If E is a subset of positive integers (for instance, numbers that are the sum of two squares, or prime numbers, or cubes) we denote as E{2} the set of elements of the form x + y, with both x and y in E. Likewise, E{3} is the set of elements of the form x + y + z with x, y, and z in E. This easily generalizes to sums consisting of n terms, with the notation E{n}. Usually, E has some parameter k attached to it, for instance E is the set of numbers that are a k-th power of a positive integer, as in the Waring problem. When needed, we use the notation E{n, k} to put emphasis on the parameter k as well. With this notation, solving the Waring problem (in its original version) consists in finding the smallest number of terms n = g(k) such that E{n, k} is the set of all positive integers, where E is the set is of numbers that are a k-th power of a positive integer.
Here we will be using a different version of E that generalizes the Waring problem. In short, we consider the case where k is any real number larger than 1, not just an integer. In particular, here E is the set of integers that can be written as INT(x^k) where x is a positive integer, ^ denotes the power function, and INT is the integer part function (also called floor function.) If k is an integer, this is identical to the Waring problem, and we don’t need to use the INT function.
Generally speaking, we are dealing with a coverage problem: Trying to cover all integers by sums of elements belonging to a very small (yet infinite) subset E of integers. The more sparse the elements of E, the larger the number of terms (the number n) in the sum needed to cover all integers. The concept of number density or scarcity is explained here.
Spectacular Result
To keep you further interested, let me state a surprising result that I obtained when doing this mathematical research. It is not proved, so it is a conjecture, and further discussed in section 2:
While you need only 4 terms (n = 4) to cover all integers if k = 2, and 9 terms (n = 9) if k = 3, and 19 terms (n = 19) if k = 4, the largest value of k that will result in covering all positive integers with only 2 terms (n = 2) is k = 1.340368108. If k is a tiny, tiny, tiny bit larger than that value, the integer 73 is the first number that fails to be covered, and thus you need to increase n from 2 to 3 for full coverage. That special value of k — the threshold beyond which n = 2 stops working — is actually equal to log(63) / log(22).
New Generalization of Golbach’s Conjecture
If instead, E is the set of all prime numbers, we would be dealing with the Goldbach conjecture (still unproved) stating that E{2} is the set of all even positive integers, or in other words, that any even integer is the sum of two primes. Back in 2008, I tried to solve this conjecture using a combinatorial approach, but have so far only written an introduction that could be useful to handle this problem: you can download the first 10 pages here (PDF document.) The picture below is from the Wikipedia entry.
If you want to cover all even integers by numbers of the form INT(p^k) + INT(q^k) where p and q are primes, Goldbach’s conjecture states that k = 1 will do. Here k is a positive real number. A weaker version of Golbach’s conjecture is to find a value of k, smaller than 1, that will do. A stronger version is to find a value of k, larger than 1, that will do. An open problem is to find the largest possible k that will do, and we know that the k in question must be between 1 and 2. Studying this problem for real values of k (instead of integers) is another direction worth exploring to solve the Goldbach conjecture. This is also true for the related Waring problem.
The fact that integers of the form INT(x^k) with x being a positive integer and k = log(63) / log(22) are far less abundant than prime numbers, yet cover all integers when considering the sums of two of them, makes you think that the Goldbach conjecture is not only true, but that a stronger version of it with some k > 1, is most likely true as well.
New Generalization of Fermat’s Conjecture
The Fermat Conjecture was proved in 1994, after 350 years of research. There is a still one million dollar award offered to whoever solves a more general version of this conjecture, see last section in this article. We propose here a different generalization that fits with our general framework. If E is the set of integers that are the k-th power of a strictly positive integer (taking the integer part of x^k as usual, if k is not an integer), the conjecture states that for an integer k larger than 2, then E{2, k} has no intersection with E. We know that if k = 2, the intersection contains an infinite number of integers. The main result in this article (still a conjecture) implies that if k is smaller than log(63) / log (22), then the intersection between E{2, k} and E is equal to E. Interesting questions here are
- What is the largest k such that the intersection between E{2, k} and E is equal to E? That value of k is between log(63) / log(22) and 2.
- What is the largest k such that the intersection between E{2, k} and E contains infinitely many numbers? That value of k is between 2 and 3.
- What is the largest k such that the intersection between E{2, k} and E is not empty? Again, that value of k is between 2 and 3, but larger than the one in the previous question.
2. Generalized Waring Problem
As stated in the previous section, the problem is about whether sums of k-th power of positive integers cover or do not cover all integers. In particular, given k, how many terms are needed for full coverage? When k is an integer, we are dealing with the standard Waring problem. If k is not an integer, the k-th power is replaced by its integer part, as discussed earlier.
The main functions of interest are listed below.
Definitions
- g(k) is the minimum number of terms, given k, to cover all positive integers. See previous section.
- G(k) is the minimum number of terms, given k, to cover all positive integers except a finite number of them.
- h(n) is the largest value of k (typically a real number, not an integer) to cover all integers with only n terms.
- H(n) is the largest value of k (typically a real number, not an integer) to cover all integers except a finite number of them, with only n terms.
The functions h and H make sense particularly in the context of the generalized Waring problem. In some way, the h function is the reverse of g, and the H function is the reverse of G. I will focus here especially on h. However, in general, H and G are more interesting than h and g. In particular, there are still many unsolved problems about G, and a fortiori about H.
Main Results
The main result here has been highlighted in the past section, see “spectacular result.” It is the fact that h(2) = log(63) / log(22). I explain in the following section (Algorithms) how this result was obtained, and how to efficiently obtain similar results for h(3), h(4), and so on, using machine learning techniques and fast algorithms..
In general, h(n) = log(p(n)) / log(q(n)) where p(n) and q(n) are integers. While it becomes incredibly more difficult to compute these numbers as n increases, it only requires efficient algorithms, as described in the next section. However, proving or disproving that these results are mathematically correct, might be difficult or impossible. Even proving that it is impossible to prove or disprove these results, might be impossible.
The fact that h(n) = log(p(n)) / log(q(n)) involves only integers for p(n) and q(n), is itself depending on whether all solutions of some special equations are transcendental numbers or not, which could be a conjecture of its own. Also, I implicitly assumed that h (just like g) is a strictly increasing function, meaning that h(n) < h(n+1) and that g is also strictly increasing even when k is not an integer. However, this is also just a conjecture, maybe not so easy to prove despite being intuitive, and maybe not even true.
Of particular interest is the case h(4). Since any positive integer is the sum of g(2) = 4 squares (k = 2), and the sum of g(3) = 9 cubes (k = 3), and since these numbers 4 and 9 can not be lowered, it means that h(4) must be between 2 and 3. Any data scientist worth her grain of salt should be able to compute the exact value of h(4), and we describe a way to do it efficiently in the Algorithm section.
Open Problems
While a general simple formula for g(k) is available when k is an integer (see the Conjecture section below), it would be interesting to compute values of g(k) when k is not an integer. Finding which integers are not covered for various n and k is also of interest. For some values of k and n, only a finite number of integers are not covered, while for other values, an infinite number of integers are not covered. Studying the asymptotic distribution of these “missing” integers is of interest. Remember that n is the number of terms in the sum, while k is the exponent.
Another problem is the number of representations. In how many ways an integer can be represented by these sums, for a particular n and k? In particular, what is the distribution for the number of representations, for integers of increasing size?
Fun Facts (Actually, Conjectures!)
Running the code in the Source Code section, with n = 2, one quickly discovers that:
- If k =1.5, the only integers that are not covered are 17, 21, 34, 56, 61, 102, 129, 138, 188, 219, 223, 231, 255, 269, 300, 331, 709, 790, 809, 902, 1131, 1284, and 1577.
- If k = 1.3403, all integers are covered.
- If k = 1.34037, the only integer not covered is 73.
- If k = 1.35, the only integer not covered is 52
If k = 1.75, infinitely many integers are not covered, but coverage increases for larger integers:
- 93.3% are covered between 1 and 1,216,079, the last one not covered being 1,216,078
- 87.5% are covered between 1 and 177,826, the last one not covered being 177,816
- 72.0% are covered between 1 and 3,161, the last one not covered being 3,161
Also if k = 1.75, between 1 and 177,818, only 8 integers can be represented (are covered) in 10 different ways: 78579, 87272 , 126136, 137767, 143628, 144206, 144441, and 158402. None can be represented in more than 10 different ways, within that range.
Finally, what happens when k gets extremely close to 1.340368108? For k = 1.340368108, we have 73 = INT(6^k) + INT(22^k). However, for k = 1.340368109, the integer 73 is not covered. Note that 22^1.340368108 = 63 (almost). Thus the largest value of k for which all integers are covered (with n = 2) is solution of the equation 22^k = 63, that is, k = log(63) / log(22). Thus h(2) = log(63) / log(22). This is the main result in this article.
This latter result is a first step towards solving the fundamental problem of identifying the sparsest subsets E of integers such that E{2} covers all integers. Remember that E{2} is the set of elements of the form x + y, where x and y belong to E.
3. Algorithms and Source Code
Naive (brute force) algorithms to make all the necessary computations are easy to derive. However, the problem is of combinatorial nature (as n increases) and thus efficient algorithms are required for n as small as 4.
Case n = 2: Sums of Two Terms
The algorithm is provided by the following source code, in Perl. Note that x^k is denoted as x**k and represents x at power k. INT is the integer part function.
The source code is available in text format, here. The element $xx[$v] represents the number of ways the integer $v can be written as a sum of two terms.
In order to identify the largest value of k that results in full coverage of all positive integers, that is h(2), you need to try various values of k using a fast converging dichotomic search. This adds one extra loop on top of the two loops on x and y. Then to find the exact value of h(2), proceed as in the last paragraph in the Fun Facts subsection,
Case n = 4: Sums of Four Terms
This involves four loops on x, y, z, w to compute v = INT(x^k) + INT(y^k) + INT(z^k) + INT(w^k), but it can be done more efficiently. I suggest to proceed as follows:
- Step 1: Compute all integers smaller than a pre-specified threshold m, that are covered by INT(x^k) + INT(y^k), and store them into some array A,
- Step 2: Then perform a double loop (on p and q) on the elements of A to find all integers smaller than m, that can be written as p + q with p and q both in A.
For large values of k, you could run into memory issues, and a distributed architecture could help. Or maybe a quantum algorithm?
Also, the same strategy – breaking sums into partial sums – can be used to handle larger values of n.
4. Related Conjectures and Solved Problems
Even for integer values of k (the standard Waring problem) many values of G(k) are still unknown (see here), and it is an area of active research. As for g(k), we have the following formula (if k is an integer):
where the brackets represent the integer part function, also denoted as INT throughout this article. This result is based on the following conjecture:
No results are known for h(n) and H(n) except those mentioned in this article, that is, the conjecture about h(2). Likewise, no results are known for g(k) and G(k) if k is not an integer.
The integer part function has many surprising properties, see here. Among others, there is a number x = 1.3064… (Mill’s number) such that for any integer n, INT(x^(3^n)) is always a prime number. See also here and here for other interesting facts about the integer part function. I also proved in 1988 — the result was published in Journal of Number Theory — that if F(n) = n − F(F(n − 1)) with F(0) = 0, then F(n) = INT( (n + 1) (−1 + SQRT(5)) / 2 ). Finally the INT function is associated with equidistributed sequences, with Euler’s function, and even has its own Fourier series.
The One Million Dollar Conjecture
Finally, I can not finish this article without mentioning Beal’s conjecture. There is a $1,000,000 prize attached to it, see here. It is about a generalization of Fermat’s last theorem (discussed in the first section in this article) though it is about a different type of generalization than the one that I discussed.
An AMS-appointed committee, the Beal Prize Committee, will recommend awarding this prize for either a proof or a counterexample of the Beal Conjecture published in a refereed and respected mathematics publication. The prize money is being held by the AMS (American Mathematical Society) until it is awarded. The spendable income from investment of the prize money is used to fund the annual Erdős Memorial Lecture and other activities of the Society that benefit early-career mathematicians.
Along the same line, I once offered a $500,000 prize to anyone proving or disproving the fact that the digits of the number Pi are random. I am currently working on the definition of “random”, and I might again open this competition in the future.
For other interesting conjectures (no award attached), click here.
For related articles from the same author, click here or visit www.VincentGranville.com. Follow me on LinkedIn.
DSC Resources
- Services: Hire a Data Scientist | Search DSC | Classifieds | Find a Job
- Contributors: Post a Blog | Ask a Question
- Follow us: @DataScienceCtrl | @AnalyticBridge
Popular Articles
