6

I suspect that certain problems regarding the base 10 representation of natural numbers may be undecidable simply because there's no way to even start.

Take any exponentially growing sequence like $16^n.$ We may ask whether this sequence ever contains a palindrome. If we check the first 100 terms and there's no palindromes, it's unlikely there will ever be. An $m$ digit number where the digits are roughly random has probability $10^{-m/2}$ of being a palindrome, so the probability of at least one palindrome after the first hundred terms is $$\sum_{n \ge 101} 10^{-\log_{10}(16^n)/2} = \sum_{n \ge 101} 4^{-n} < 2^{-200}. \tag{$*$}$$ However, this is not a rigorous proof.

Looking up other simple questions regarding base 10 representations, it seems no one has an idea on how to start, people can only add more and more conjectures to the pile. As a result, the subject doesn't receive serious attention. If we do see someone claim progress of the sort, it's usually a crank writing nonsense.

If this is unprovable, how do we show it's unprovable? For the specific problem of showing there's no palindromes in a fast growing sequence for which we have ruled out enough terms that the probability computed like in $(*)$ of one appearing later on is low, maybe we can emulate a Turing machine within the digits. However, I don't think there's a way to do this with just one base and exponent, maybe $c_1^{p_1} + \dots + c_n^{p_n}$ for polynomials $p_i(x_1, \dots, x_n)$ and $x_i \ge k_i$ could contain enough information inside the digits of the sum.

In the case it turns out that even showing unprovability is unprovable, we get a general hierarchy of unprovability indexed by ordinals where $0$ is the original statement, $\alpha + 1$ is the statement that $\alpha$ is undecidable, and $\lambda$ is the statement that $\lambda_n$ is undecidable for all $n$ where $\lambda = \lim\limits_n \lambda_n$ is a limit ordinal. Can any ordinal be established? The standard remark here is if we show undecidability on any level, the statement is true since if it's false, there's a counterexample (palindrome or other undesired structure appearing), so a proof which consists of stating the counterexample and checking it exists.

Community
  • 1
Display name
  • 745
  • 2
    The short answer is that if we're stumped by a problem, then it means we don't know how to make progress on it, by any means. One cannot expect a general method for attacking intractable problems. But you might be interested in related MO questions such as True by accident (and therefore not amenable to proof), Knuth's intuition that Goldbach might be unprovable, and What is the depth of the "provability heirarchy"?. – Timothy Chow Nov 24 '22 at 05:06
  • Maybe I misunderstand your question, but if you show these problems are unsolvable, then there are no examples of, say, a palindrome (otherwise exhibiting an $n$ would be an easy solution), and in fact the problem was solvable after all. I think maybe one could consider something like "a proof of the fact of its negation would take at least $10^{10^{10}}$ symbols", in which case it is in practice unsolvable. – Pierre PC Nov 24 '22 at 08:53
  • @PierrePC Your remark is my last sentence, I just mixed and matched unsolvable, independent, and undecidable carelessly. – Display name Nov 24 '22 at 08:56
  • Indeed, somehow I missed your remark, my apologies. You do not really respond to it though, what do you have in mind when you mean "unsolvable" then? – Pierre PC Nov 24 '22 at 09:42
  • 4
    "As a result, the subject doesn't receive serious attention." There might be more than one reason why the subject doesn't receive serious attention. – Steven Landsburg Nov 24 '22 at 15:07
  • Discussed here: https://math.stackexchange.com/questions/156669/freeman-dysons-example-of-an-unprovable-truth – Jeffrey Shallit Nov 25 '22 at 14:57
  • @PierrePC I mean unprovable, or independent of the axioms of PA. Updated the question text. – Display name Nov 26 '22 at 06:16
  • 3
    Using the symbol $\omega$ to represent an arbitrary limit ordinal is like using the symbol $\pi$ to represent an arbitrary real number. I'd suggest using $\lambda$ instead. – Joel David Hamkins Nov 26 '22 at 14:32
  • @StevenLandsburg There's also the fact that patterns in decimal representation don't have any further applications much like the truth of Fermat's Last Theorem doesn't have any (yet solution attempts led to many useful tools and results), but that's a given. – Display name Nov 27 '22 at 01:51

1 Answers1

2

Let me introduce a different example of such kind of issue that I've found this year.
Months ago, I submitted to the OEIS a new sequence of integers concerning perfect powers (see A3530255), listing the smallest perfect powers written as the concatenation of any permutation of the integers from $1$ to $n$ (for any given $n$). Now, there are $72$ perfect squares that are smaller than $10^{17}$ and many others between $10^{22}$ and $10^{29}$, but no perfect power above $2$ has been detected after several hours of computations.

We could argue that the only perfect cube belonging to $A353025$ is $A353025(1):=1^3$, but this approach would probably lead to a wrong guess, since the conjecture is almost certainly false by assuming a standard distribution of perfect powers in that context; simply we do not have enough computing power to find a counterexample even by performing dozens years of computation on a standard CPU.
On the other hand, we are able to construct examples that prove that no cubes belong to a given sequence under certain constraints that we could have missed by assuming an uniform distribution of cubes among numbers that are not consecutive integers (I am not saying that a counterexample wouldn't be absolutely resonable in this range, but that we cannot exclude for sure such a theoretical scenario)... (e.g., let us take any subset of the following set of numbers in the range ($1$-$99$) $\{2, 5, 6, 10, 14, 15, 18, 20, 22, 26, 30, 34, 35, 38, 40, 42, 45, 46,50, 54, 55, 58, 60, 62, 65, 66, 70, 74, 78, 80, 82, 85, 86, 90, 94, 95, 98\}$ and then let us concatenate every permutation of the selected subset).
Question: How many perfect cubes (from $1$ to $70^+$ digits) will we find? Answer: None, since no cube can belong to any of the above mentioned congruence classes $\pmod {100}$.

The issue here is to support a fuzzy (ex ante) probability theory that the standard distribution of perfect powers among natural numbers holds for the sequence above, but how could we (partially) disprove the theoretical occurrence of any hidden constraint as the one that I've maliciously introduced above?

For these reasons, I've uploaded on the arXiv a preprint (see
On some open problems concerning perfect powers) conjecturing the opposite statement (i.e., all the $A353025(n) : n > 1$ are perfect squares only), even if (without introducing unknown artificious constraints as the above) it would be "more" reasonable to assume that there could be infinitely many perfect cubes, squares of squares, and so forth.

Gerry Myerson
  • 39,024
Marco Ripà
  • 1,119
  • 4
  • 18
  • Although it's not mentioned in the question, I believe OP is working with the base ten representations of the integers. It might (or might not) be interesting to consider the same questions for other bases. E.g., the concatenation of $1,2,3$ in base two is $11011$, which is a perfect cube. – Gerry Myerson Nov 27 '22 at 00:14
  • Of course, you are right. – Marco Ripà Nov 28 '22 at 01:24