The efficient-prime finite-control conjecture for integer complexity

For real α\alpha and integers m<nm<n, define S(m,n,α)S(m,n,\alpha) to mean that if

kαlogk\|k\|\leq \alpha\log k

for every integer kk with m<k<nm<k<n, then

nαlogn.\|n\|\leq \alpha\log n.

For a prime pp, let vpv_p denote the pp-adic valuation. The conjecture concerns the pp-adic behavior of efficient primes.

The efficient-prime finite-control conjecture. For any α>2log2\alpha>\frac{2}{\log 2}, there is a finite set of primes SαS_\alpha such that, for any mm, if vpv_p is sufficiently large for all pSαp\in S_\alpha, then S(m,n,α)S(m,n,\alpha).

The source says that a careful study of efficient primes is expected to prove this assertion, but gives no resolution. The quantification and the role of nn in the final condition follow the supplied statement, whose formulation may warrant checking.

Sources & referencesView supporting material

Primary source

Joshua Zelinsky, “Upper Bounds on Integer Complexity”, arXiv:2211.02995 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.