Open Problems

I’ve gathered some problems I haven’t been able to completely resolve.

If you decide to try these, or if you find that they’ve been solved in literature somewhere, I’d be interested to hear about them. I’ll include a brief summary of progress.

Problem 1

Suppose you have two sets $A$ and $B$ of natural numbers.
Write $A ⊥ B$ if the sets $b_{1} A \cap b_{2} A$ have zero natural density, whenever $b_{1}, b_{2}$ are different elements of $B$ . In other words, $A$ has nearly disjoint $B$ -dilations.
Then the upper density of $A$ is at most
$\overset{―}{d} (A) \leq {(\sum \frac{1}{b})}^{- 1}$

See the following posts for context: 1 2

The first post basically proves it for nice $B$ for which there exist $A$ such that the dilations $b A$ are disjoint and such that $A \times B = N$ . Erdős and Saffari call these “direct factors”.
This case extends to $B = N$ by a limiting argument.

The second post proves it for the case in which $\sum \frac{1}{b} = \infty$ and such that the elements of $B$ are pairwise coprime. This contains the case $B = P$ being the set of primes.

I’ve proved it by a few arguments for the cases (for example)

\begin{aligned} B & = {1, 2, 3} \\ B & = {1, 2, 5} \\ B & = {1, 2, 3, 4} \\ B & = {1, p, q} when p < q < p^{2} \end{aligned}

The general case, as well as the special case $B = {1, p, q}$ , remain open.

Problem 2

Fix a base $b > 1$ and a natural number $x_{1}$ .
Let $x_{n + 1} = x_{n} + f (x_{n})$ where $f (x)$ is the sum of the base- $b$ digits of $x$ .
Similarly create the sequence $y_{n}$ starting from a natural number $y_{1}$ .
Then there exists an integer $i$ such that $x_{n} = y_{n + i}$ for all large $n$ iff $gcd (x_{1}, b - 1) = gcd (y_{1}, b - 1)$ .
In the binary case, there always exists such an integer $i$ .

It seems like there’s some simple proof that I’m just totally overlooking here.

Let tetration be written as $^{n} a = a^{a^{\dots^{a}}}$ , where there are $n$ levels in the tower.

Here’s a proof (minus computer calculation) that, in the binary case, any starting values $a_{1}, b_{1} <^{2000} 2$ will both eventually be mapped to the same value.

Fix $K$ and initialize the range $[1,^{K} 2 - 1]$ .
Any integer in this range will eventually be mapped to the range $[^{K} 2,^{K} 2 +^{K - 1} 2 - 1]$ , since the max bit count in the first range is $^{K - 1} 2$ .

From there it gets a little uglier, this range maps into $[^{K} 2 +^{K - 1} 2,^{K} 2 +^{K - 1} 2 - 1 + 1 +^{K - 2} 2]$ .
Continuing on, you get ranges of the form $[^{K} 2 +^{K - 1} 2 + \dots +^{J} 2 + U,^{K} 2 +^{K - 1} 2 + \dots +^{J - 1} 2 + V]$ which get successively narrower, and you stop once the value of $V$ exceeds $^{J - 1} 2$ . That only realistically happens for $J - 1 \leq 4$ , since $^{5} 2$ is astronomically big.

Now, that doesn’t reduce the problem to one integer, rather a small range (seemingly linear in $K$ ) which we can manually test to ensure they all converge to one trajectory. To do that we separate off the sum of powers of two down to $^{5} 2$ and treat the bit count of those separately.

My super old Facebook post on this says that every starting value under $^{2000} 2$ is eventually mapped to $^{2000} 2 +^{1999} 2 + \dots +^{5} 2 + 838365944$ .

Problem 3

Say $α$ is an algebraic number.
Is there always a finite sequence of polynomials $f_{1}, f_{2}, \dots, f_{k}$ all of which having integer coefficients and rational zeros¹ which, when composed, has $f_{1} (f_{2} (\dots f_{k} (α) \dots)) = 0$ ?

If $α = \frac{p}{q}$ is rational, the length one sequence $f_{1} (x) = q x - p$ works.

What if $α$ is a quadratic irrational, say $A α^{2} + B α + C = 0$ ?

Then the sequence $f_{1} (x) = x + C$ and $f_{2} (x) = x (A x + B)$ works.

I posted this some years ago on the actually good math problems Facebook group. There, Jordi Ribes provided a working sequence for the cubic case:

Any cubic x^3+ax^2+bx+c divides the polynomial (x+a/3)^2((x+a/3)^2-(a^2-3b)/3)^2-((2a^3-9ab+27c)/27)^2. This comes from computing the depressed cubic t^3+dt+e (where d,e depend on a,b,c) through the change t=x+a/3, and noting that t^3+dx+e divides t^2(t^2+d)^2-e^2. So f_1(x)=(x+a/3)^2, f_2(x)=x*(x-(a^2-3b)/3)^2, f_3(x)=x-((2a^3-9ab+27c)/27)^2.

Seems interesting. The cases with degree $\geq 4$ are open.

Edit added 7/3/2024. Oops! ↩