[Math] Has there been any new development on the Freudenthal Problem

Question

Background

I have seen a few variants of this Sum-and-Product puzzle in the past. The premise of these puzzles is as follows

Sam hears the sum of two numbers, Polly the product. The numbers are known to be between m and M.

S: "You don't know the numbers"

P: "That was true, but now I do"

S: "Now I do too"

What are the numbers?

A set of papers from 2006 refer to this as the Freudenthal Problem Freudenthal(m,M). I have been specifically interested in classifying solutions when $m=3$, and $M$ is unbounded.

Assuming a modified form of Goldbach's conjecture, the authors prove that whether the numbers are known to be distinct or not does not change the solutions when $m=2$ and $m=3$, so I have removed their superscript distinguishing the case.

The authors also give a rather naive algorithm that enumerates solutions ordered by sum. They generate solutions for Freudenthal(3,*) up to a sum of 50,000, and find that there are 804 stable solutions, and 288 phantom solutions that rely on the presence of an upper bound.

My own findings

I wrote a program that very efficiently generates solutions, also ordered by sum, and improved the highest sum by an order of magnitude overnight.

I then defined the "Freudenthal Partition Function" $F(s)$. The domain of this function is any sum $s$ which allows the first statement by Sam. The value $F(s)$ is the number of options remaining in Sam's mind after Polly's statement.

There is a lot to unpack in this function, so I will go into detail.

Domain of $F$

With $m=3$, the products which allow Polly to immediately deduce the numbers are any of the following:

• Odd semiprimes
• 4 times an odd prime (numbers must be 4 and p)
• 2 times the square of an odd prime (numbers must be p and 2p)

For Sam to make his first claim, the number cannot be the sum of two odd primes, sum of a prime and 4, or 3p for some p. What remains is the set $S$, which is the domain of $F$.

Assume the Goldbach conjecture so that all even numbers are eliminated from $S$ outright. Then $s\in S$ iff $s$ is odd, $s-4$ is composite, and $s\ne 3p$ for some prime $p$. This set can be efficiently generated.

Computing $F(s)$

Start with a list of all even integers. Iterate over all pairs $\{(s,a)\mid s \in S, a \in \mathbb{Z}, 3 \le a \le s/2\}$ and place a tally next to $a(s-a)$. For computability's sake, proceed lexicographically by $s$ then $a$.

After this procedure passes $s_0$, all tally counts on integers up to $3s_0-9$ are stable. Define the set $P$ to be all the integers with exactly one tally.

$p \in P$ has the following properties:

• $p$ is not uniquely factorable into two divisors in the set $\{z\mid z \in \mathbb{Z}, z\ge 3\}$ (guaranteed since they were reached from $S$).

• $p$ has a unique divisor pair $\{d,p/d\}$ such that $d + p/d \in S$.

Equivalently, if Polly was told the number $p$, then the first two lines of the puzzle are satisfiable.

To compute $F(s)$ given $P$, iterate over $\{a \mid 3\le a\le s/2\}$ and count the number of $a$ for which $a(s-a) \in P$.

Using $F(s)$

If $F(s)=1$, then Sam, upon hearing Polly's statement, can deduce the numbers. This corresponds to a solution to the puzzle. Other claims I will make about the behavior of $F(s)$ are just conjectures.

If $F(s)=0$, then there seems to always exists some upper bound $M$ such that an integer which had two tallies loses one, and $P$ gets a new element which causes the puzzle to be satisfiable. These correspond identically to what the authors of the 2006 paper called "phantom solutions". Indeed, for $s<50,000$, there are 804 instances where $F(s)=1$, and 288 instances where $F(s)=0$.

A graph of $F(s)$ is found here for $s$ up to around 260,000. The function has three very distinct branches, corresponding to congruence classes mod 3. The bottom branch, which produces all known solutions, has $s\equiv 2 \pmod{3}$.

The solution pairs themselves

A list of the 3141 smallest pairs ordered by sum can be found here. I list the even number, then the odd number. The same pairs ordered by even number can be found here, and is more illuminating.

A notable oddity is $(4, 137233)$, the only currently-known pair to include the value 4. This was missed entirely by the original papers.

The pairs seem to all be of the form $(4^np,q)$, where $n>0$, $p$ is either 1 or prime, and $q$ is either prime or the product of a small number of primes. All prime factors of $p$ and $q$ are congruent to $1 \pmod{3}$.

Non-solutions and what we can learn from them

For every $s$, there are $F(s)$ pairs that can be considered "candidate solutions." If $F(s)>1$, they are not solutions, but in the lowest branch they share many properties of solutions.

For example, $F(53) = 2$, and the contributing pairs are $(4,49)$ and $(16,37)$. This could have allowed one to see that 4 is viable as one of the two numbers, even without finding the first example of $(4, 137233)$.

Looking at all candidate solutions for $s\equiv 2 \pmod{3}$, we find a very small set of exceptions to the $(4^np,q)$ trend.

The exceptional pairs with sum less than 500,000 are

• $(32,27)$
• $(128,9)$
• $(512,3)$
• $(2048,3)$
• $(32768,3)$
• $(32768,27)$

All are $(2^k,3^l)$ for $k$ odd and $l$ small. They all have $F(s)>1$ for their sum, so they are not solutions, but they lie in the bottom branch of the partition function and allow the puzzle to proceed through its first two statements.

I checked (inefficiently) all pairs $(2^k,3^l)$ for odd $k\le 31$ and $l\le 10$, and found 5 other pairs which allow the first two statements to be satisfied, but in every case $F(s)>1$. It remains open whether there exists a true solution with this form.

Edit: I have a program running to find pairs $(2^k,3^l)$ for which the first two statements can be satisfied, and for each pair, search for a witness to $F(s)>1$. For $k\le 219$ and $m\le 25$, there are 13 pairs with no witness of the form $(4^n,q)$. The much more computationally intensive task of confirming absence of a witness of the form $(4^n p,q)$ is likely intractable if the pair is a solution. Witnesses have been found for the smallest 10 pairs, the first pair with no known witness yet is $(2^{187}, 3)$.

Results for $m\ge 4$

I used the same program to examine other values of the lower bound, with what I believe were the appropriate changes and assumptions. The header comment can help others verify the correctness. I did not find any solutions, in agreement with the conjecture put forth in in the papers. Graphs of the corresponding Freudenthal Partition Functions diverge from 0, leaving no branch which could be believed to provide solutions.

So, my question to mathoverflow is: Has there been anyone else thinking about this problem, and do they have results that supplement/contradict/dwarf those I have gathered?

Asymptotic behavior of $F(s)$

I did some asymptotic analysis of $F(s)$. For a given $s$, I determined all the products with at most 3 odd factor sums such that one of those sums is $s$, and what numbers on the order of $s$ must be prime for $F(s)$ to increase by 1. This gives remarkably good fits for the three congruence classes. To reduce noise, I show here a moving average of $F(s)$, averaging the nearest hundred values in the same branch.

Notably, those $s \equiv 2 \pmod{3}$ have no growth at order $s/\log(s)^3$, always requiring an additional number to be prime and resulting in asymptotic growth at order $s/\log(s)^4$. This keeps $F(s)$ very near zero for those values we have seen, but means that $F(s)$ still grows without bound for these $s$.

This has potential to imply that there are only finitely many solutions, although such a claim is still far off. I don't know how best to determine $\liminf\limits_{s \to \infty} F(s)$.

Arithmetic progressions $s_a$ with $F(s_a)$ exceptionally low

If one rephrases the argument which gave the asymptotic formula in terms of the probability $F(s)=1$, they predict that there are only finitely many solutions, and that over 95% have been seen by the point $s=100,000$. We know at least the latter to be false, so there are systematic failures of the argument.

The leading order contribution to the lowest branch of $F(s)$ counts the instances where three things hold:

• $s=4^kp+q$ for primes $p$ and $q$ with $k\ge 2$
• $s^\prime=4^k+pq \not\in S$, that is, $4^k+pq-4$ is prime.
• $s^{\prime\prime}=4^kq+p \not\in S$, that is, $4^kq+p-4$ is prime.

Note that $s^{\prime}-s=(4^k-p)(q-1)$ and $s^{\prime\prime}-s=(4^k-1)(q-p)$. The factor $4^k-1$ is independent of $p$ and $q$. When $s-4$ shares a factor with $4^k-1$, $s^{\prime\prime}$ is not prime for any $p,q$.

Since $s\equiv 2\pmod{3}$ is necessary, $s-4$ cannot be a multiple of 3. If we define $k_m(s)$ to be the smallest $k\ge 2$ such that $(4^k-1,s-4)=1$, then we can refine the first bullet point above:

• $s=4^kp+q$ for primes $p$ and $q$ with $k\ge k_m(s)$

We then refine our prediction about the asymptotic behavior of the low branch of $F(s)$:

$F(s) \sim s\log(s)^{-4}4^{-k_m(s)}$

We may define $g(k)$ to be the smallest value not divisible by 3 and sharing a factor with $4^n-1$ for all $n\le k$, so $k_m(g(k))=k+1$, then $g(2)=5$, $g(3)=35$, $g(5)=385$, etc. Each defines an arithmetic progression with exceptionally low values of $F(s)$. Specifically,

$s_{a,k}=\left\{\begin{array}{11}
(6a+1)g(k)+4 & g(k)\equiv 1\pmod{6}\\
(6a+5)g(k)+4 & g(k)\equiv 5\pmod{6}
\end{array}
\right.$

Determining whether $F(s)$ takes the value 1 often, we must know the growth pattern of $g(k)$.

$F(s_{0,k})\sim g(k)\log(g(k))^{-4}4^{-k}$

This appears to grow unbounded, though erratically. It returns to values near 1 at $k=30$ and $k=60$ before jumping upward. I conjecture that $\liminf\limits_{s \to \infty} F(s) = \liminf\limits_{k \to \infty} F(s_{0,k})$.

I have checked the value of $F(s_{a,30})$ for $a \le 500$ and found 4 probable zeros and 7 probable solutions, the largest of which is $(4^{31}*459703, s_{34,30}-4^{31}*459703)$. This might be the largest solution. (Update: I did finish the check of the less-probable cases, completing a proof that this pair is a solution. The proof is found here).

To determine $g(k)$, we must make a statement about the smallest prime factor of $(4^k-1)/3$.

If $k$ is composite, then the smallest prime factor of $(4^k-1)/3$ is the smallest prime factor of $(4^d-1)/3$ for some divisor $d$ of $k$. This factor is present in $g(q)$ for all $q\ge d$, so if $k$ is composite we must have $g(k)=g(k-1)$.

If $k$ and $2k+1$ are both prime, then given the recurrence $r_0=0$,
$r_{n+1}=4r_n+3 \pmod{2k+1}$, we have $r_k=0$, and so $4^k-1$ is divisible by $2k+1$.

If $k$ is prime and there is not a value of the form $ck+1$ for which the recurrence relation above holds, then the smallest prime factor of $(4^k-1)/3$ might be $(2^k+1)/3$. This happens for $k=7,13,17,19,31,61,…$. At the moment I don't have a full understanding of why primality of both $k$ and $6k+1$ is able to predict a factor of $6k+1$ in $4^k-1$ when $k=37$, but not when $k=17$.

The jumps upward in $g(k)$ when it must now include a factor of $(2^k+1)/3$ have increasing magnitude and seem to indicate unbounded growth of the expression $g(k)\log(g(k))^{-4}4^{-k}$, although proving this is beyond my ability.

Unbounded growth of this expression would imply with high certainty that there are finitely many solutions to the Freudenthal problem Freudenthal(3,*). Is there an approach to proving this?

Answer 1

I have a new result that might be a step towards proving there are infinitely many solutions. We show that there is an infinite sequence of values for which $F(s)$ is at most 1.

Consider $s_k = 2^{2^k} - 5$ for $k \ge 3$.

We have stated that a number is in $S$ if it is not $4 + p$ for prime $p$, and is not $3q$ for prime $q$. We also stated that a product is in $P$ iff exactly one divisor pair has sum in $S$. We will show that $s_k \in S$ and at most one of the products $l (s_k - l)$ is in $P$.

$s_k$ is not a multiple of 3, so the latter condition for inclusion in $S$ is always satisfied.

Subtract 4 to get $2^{2^k} - 9$. This number is not prime. It is divisible by 7 is $k$ is even, and 13 if $k$ is odd. This can be proven by induction. Therefore $s_k \in S$ for all $k \ge 3$.

Consider ways to sum to $s_k$. Since $s_k$ is odd, all pairs of summands must consist of one even and one odd number. Let the even number be $a'$, the odd number $b$. Let $v_p(x)$ be the p-adic valuation of $x$. Define $m = v_2(a')$ and $a = 2^{-m} a'$. We know $m \in [1, 2^k)$ and $a$ is odd. We can write $s_k = 2^m a + b$.

If $a \ge 3$, write $s'_k = 2^m b + a$.

Add $s_k$ and subtract it:

$s'_k = 2^m b + a + (2^m a + b) - (2^{2^k} - 5)$

Factor and subtract 4:

$s'_k - 4 = (2^m + 1)(a + b) - (2^{2^k} - 1)$

Since $m < 2^k$, we know $2^m + 1$ shares a nontrivial factor with $2^{2^k} - 1$. This factor divides $s'_k - 4$, and thus $s'_k - 4$ is composite. Furthermore, $s'_k$ is congruent mod 3 to $(-1)^m s_k$, so it is not a multiple of 3. $s'_k \in S$, so the product $2^m a b$ with $a \ge 3$ has at least two factorizations with sum in $S$, and cannot be in $P$.

If $a = 1$, we have $b = 2^{2^k} - 5 - 2^m$. For $m \ge 3$, we can examine $b$ modulo $y = 2^{2^{v_2(m-2)}} + 1$.

Write $2^m$ as $4 * 2^{m-2}$, and then write $2^{m-2}$ as $2^{2^{v_2(m-2)} m'}$ with $m'$ odd. Modulo $y$, $2^m = 4(-1)^{m'} = -4$. Since $2^k > m$, we know $2^{2^k}$ is $2^{2^{v_2(m-2)}}$ raised to some even power. Thus, modulo $y$, $b = 1 - 5 + 4 = 0$. We found a divisor of $b$.

When $m$ is even, the alternate factor sum $y + 2^m (b/y)$ is 1 mod 6, and thus is in $S$, so $2^m b \not \in P$.

When $m$ is odd, $y = 3$, so we know $b$ is a multiple of 3. Define $r = v_3(b)$, $z = 3^{-r} b$. We know $r$ is at least 1 and $z$ is congruent to either 1 or 5 mod 6. If $z \ge 5$, we can write the factor sums $s'' = z + 3^r * 2^m$ and $s'''= 3^r + 2^m z$.

If $z$ is 1 mod 6, $s''$ is 1 mod 6. If $z$ is 5 mod 6, $s'''$ is 1 mod 6. Either way, one of the two values is in $S$, so $2^m 3^r z \not \in P$.

$z = 1$ occurs when there is a solution to the diophantine equation $2^{2^k} - 5 = 2^m + 3^n$.

I am to believe that there is exactly one solution for $k \ge 3$. When $k = 3$, we have $2^8 - 5 = 251 = 8 + 243$. In this case, we can consider the alternate factor sum $27 + 72 = 99$, which is in $S$. A result told to me here claims there can be no other cases where $z = 1$ can occur.

We have eliminated $a \ge 3$ unconditionally and $a = 1$ when $m \ge 3$. We are left with only one possible pair of summands: 4 and $2^{2^k} - 9$. I don't have a proof that $4(2^{2^k} - 9)$ is or is not in $P$. By my counts it certainly can be, if 3 derived numbers are all prime. That is a rare event, and it would be reasonable for it never to occur given how quickly $2^{2^k}$ grows. However, our initial claim was that at most one derived product is in $P$. We have shown that.

This completes the proof.