Conjecture on collapse and average logarithmic integer complexity

At least 2 years old · documented by

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.

References

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.