Conjecture on collapse and average logarithmic integer complexity

Let fˉlog(n)\bar{f}_{\log}(n) denote the average logarithmic integer complexity, and let αave\alpha_{ave} be the corresponding limiting average complexity. Say that a number nn collapses when powers of nn have unexpectedly low integer complexity. The conjecture is stated in the context of treating nkn^k as random.

Collapse conjecture. If

fˉlog(n)<αave,\bar{f}_{\log}(n)<\alpha_{ave},

then nn is unlikely to collapse.

This claim appears inside an ignored passage and is presented heuristically rather than as a proved theorem. The source supplies no resolution, so it remains open.

Sources & referencesView supporting material

Primary source

Qizheng He, “Improved Algorithms for Integer Complexity”, arXiv:2308.10301 (2023).

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.