Conjecture on collapse and average logarithmic integer complexity
Conjecture on collapse and average logarithmic integer complexity
Let denote the average logarithmic integer complexity, and let be the corresponding limiting average complexity. Say that a number collapses when powers of have unexpectedly low integer complexity. The conjecture is stated in the context of treating as random.
Collapse conjecture. If
then 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.