A function that is defined everywhere but has unknown values - MathOverflow [closed]

A function that is defined everywhere but has unknown values

2012-09-14T11:13:54Z

For pedagogical purposes I am looking for a function $\mathbb{N}\to\mathbb{N}$ that is defined everywhere but has most of its values unknown. Although such a function cannot be simple by definition, I nevertheless hope that there is such a function that is simple to explain.

I have listed a few examples myself which I am not very satisfied with for various reasons:

The halting function. This function is one of the uncomputable functions (probably the only uncomputable function) that is most easy to explain.

My problem with this one is that it involves computability theory, and I do not want to draw in computability if that is not necessary.
The busy beaver function. Also an uncomputable function. Which is a bit harder to explain.
The function that is $1$ everywhere if Goldbach's conjecture is true, and $0$ everywhere if Goldbach's conjecture is false.

Problem: this is a constant function.
The function that is $1$ if $n$ is even and every even number is the sum of $n$ primes, or $n$ is odd and every odd number is the sum of $n$ primes. (And $0$ in all other cases.) For $n=2$ I believe this is the Goldbach conjecture, and for $n=3$ I believe this is the weak Goldbach conjecture. So this function is already a headeache for $n=2,3$, let alone for $n>3$.

Personally, this would be my favourite if it wasn't so baroque and over the top.
The Collatz characteristic function. $1$ if the Collatz sequence converges, $0$ if it does not.

Problem: too easy to verify on individual arguments. And it has little illustrative value because the Collatz characteristic function seems to be $1$ everywhere. (Emphasis on "seems".)
The function $\mathbb{N}\to\mathbb{N}_0:n\mapsto \mbox{number of living people aged}(n)$.

Problem: depends on the real world. Not really a pure Platonic math function. (And function values change constantly throughout time.)

BTW: My question rules out computable functions. Values of computable functions on their domain of definition are known due to, e.g., dovetailing. (So strictly speaking, the 3rd item should be ruled out for this reason since constant functions are computable.)

Thank you.

Answer by Tony Huynh for A function that is defined everywhere but has unknown values

2012-09-14T12:00:15Z

What about the (diagonal) Ramsey Numbers, $k \to R(k,k)$? These are fairly natural to define but notoriously hard to compute. Indeed, only the first two Ramsey numbers $R(3,3)=6$ and $R(4,4)=18$ are known. We do know that $R(5,5) \in [43,49]$, which is the subject of the following joke (I may be butchering the content).

Joke. If an omnipotent alien came down to Earth and demanded that we determine $R(5,5)$ within a week, then mankind should divert all of its brainpower and resources to achieve this goal.

If on the other hand, the omnipotent alien demanded that we determine $R(6,6)$ within a week, then mankind should divert all of its brainpower and resources to destroy the alien.
End Joke.

Answer by Joel David Hamkins for A function that is defined everywhere but has unknown values

2012-09-14T12:32:31Z

Consider the function $f:n\mapsto k$, where the power set $2^{\aleph_n}$ has the form $\aleph_{\omega\beta+k}$ for some natural number $k$.

This function is everywhere defined, since the power set $2^{\aleph_n}$ must be $\aleph_\alpha$ for some ordinal $\alpha$, and every ordinal can be uniquely expressed in the form $\omega\beta+k$. The number $k$ is simply the residue of $\alpha$ modulo $\omega$, the finite part of $\alpha$ sticking above its last limit. So this function is defined at each $n$.

But meanwhile, we cannot say with certainty any particular value of $f$. If the GCH holds, then $f(n)=n+1$, but if the GCH fails in complicated patterns, then $f$ will be similarly complicated.

We cannot provably determine in ZFC---or even in much stronger theories such as ZFC + large cardinals---any particular value of $f$. Indeed, the particular values of $f(n)$ are completely independent from one another, from the perspective of what is provable in ZFC or in ZFC+large cardinals, since by Easton's theorem it is consistent with ZFC that $f$ is any function at all from $\mathbb{N}\to\mathbb{N}$. For any particular function $g:\mathbb{N}\to\mathbb{N}$, there is a forcing extension of the universe whose version of $f$ coincides with $g$.

So this would seem to be a fairly strong sense in which we do not know the values of $f(n)$ for any particular $n$.

Answer by Arthur Fischer for A function that is defined everywhere but has unknown values

2012-09-14T13:03:48Z

Kind of a cheat, but define $f : \mathbb{N} \to \mathbb{N}$ so that $f(n)$ is the initial position (to the right of the decimal point) of the first occurance of $n$ consecutive $5$s in the the decimal expansion of $\pi$, and $0$ if such does not exist.

So $f(1) = 4$, $f(2) = 130$, $f(3) = 177$, $f(4) = 24,466$, etc. I don't think I'm saying too much by claiming that as it is unknown whether $\pi$ is normal, we do not know if $f(n)$ is non-zero for all $n$.

EDIT: I honestly didn't see the almost identical answer in the comments above before posting this. It has thus been made CW.

Answer by Yoav Kallus for A function that is defined everywhere but has unknown values

2012-09-14T13:16:27Z

Your (1) could be substituted for pedagogical ease of presentation with the Conway's Game of Life "halting problem" (note that they are equivalent). That is, the function which for any starting configuration returns a value indicating whether the system eventually reaches a stationary state (return 0), periodic cycle (return 1), or never becomes stationary or periodic (return 2). You can show cool movies of Game of Life evolutions which would hopefully make it clear how unpredictable the behavior can be. The only tricky part pedagogically is assigning a number to each configuration, but that's not really that hard to understand.

Answer by Barry Cipra for A function that is defined everywhere but has unknown values

2012-09-14T19:30:22Z

How about something based on a generalized twin prime conjecture? That is, $f(n)=1$ if there are infinitely many pairs of primes that differ by $2n$ (and $f(n)=0$ if not).

Added 9/15/12: It might be worth modifying the example to say $f(n)=1$ if and only if there are infinitely many pairs of consecutive primes that differ by $2n$. That would bring it fully in line with Polignac's conjecture. It's worth noting (here, at least) that the function as originally proposed could conceivably still be identically 1 even if Polignac's conjecture were false for all $n>2$.

Answer by GH for A function that is defined everywhere but has unknown values

2012-09-14T20:23:55Z

How about this one: $f(n)=1$ if $2^{2^n}+1$ is prime, and $f(n)=0$ otherwise.

Or: $f(n)$ is the largest prime factor of $2^{2^n}+1$.

Added 1: Inspired by Barry Cipra's comment, here is a function which is unknown in principle, not just in practice: Let $r(m)$ denote the number of lattice points on the sphere $x^2+y^2+z^2=4m+1$, and define $f(n)$ as the largest $m$ with $ r(m) < n\cdot m^{1/3}$.

Added 2: Here is another function, inspired by Barry Cipra's example: $f(n)$ is the $n$-th positive integer which is a sum of three cubes (including negative cubes).

Answer by zeb for A function that is defined everywhere but has unknown values

2012-09-14T23:29:25Z

Let $f(m,n)$ be the maximum number of isolated positive real roots of a system of two equations $p(x,y) = 0$ and $q(x,y) = 0$, such that $p$ contains at most $m+1$ monomials and $q$ contains at most $n+1$ monomials ($p$ and $q$ would then be known as "fewnomial curves", with "fewnomial degrees" equal to $m$ and $n$).

It is known that $f(m,n)$ is finite for every $m,n$, and I think $f(m,n)$ could in principle be calculated if Schanuel's conjecture was known to be true. It was conjectured by Kushnirenko that $f(m,n) = mn$ (in analogy with Bezout's theorem), but later it was discovered that in fact $f(2,2) = 5$, with a worst case example due to Haas given by

$p(x,y) = x^{106}+1.1y^{53}-1.1y,$ $q(x,y) = y^{106}+1.1x^{53}-1.1x.$

It's also known that $7 \le f(2,3) \le 14$ and $f(2,n) \le 6n+5$ (these bounds and the above example are from the paper "Extremal Real Algebraic Geometry and A-Discriminants").

Answer by Jason Rute for A function that is defined everywhere but has unknown values

2012-09-15T03:57:59Z

Hilbert's 10th problem.

Let $f$ be as follows. For every multivariable integer-coefficient polynomial $p$ (properly encoded as a natural number), let $f(p)$ encode an integer solution $\bar{x}=(x_1,x_2,...,x_n)$ that satisfies $p(\bar{x})=0$. If there is more than one solution, pick the one whose dictionary order of the absolute values is lowest. If none, let $f(p)=0$. This is fairly easy to explain, and by the theorem of Davis, Matiyasevich, Putnam and Robinson, this function is not computable.

Of course, if you want to prove to your class that this is not computable, then you have a lot of work to do. However, if that is the case, I think you have a problem. You then seem to be looking for an incomputable function that you can explain to your class why it is incomputable (or "unknowable"). I don't think you can do this without logic (either computability theory or the incompleteness theorems).

And as for the incomputable functions, I think Hilbert's 10th problem is one of the easiest for mathematicians to grasp. [Although in our bug-ridden computer age, I don't think it is that hard to explain to freshman that we can't be sure a computer program won't crash. :) ]

Answer by Jason Rute for A function that is defined everywhere but has unknown values

2012-09-15T04:05:54Z

Trivial Answers:

These probably aren't helpful but...

1) Randomness: Flip a coin repeatedly and let $f(n)$ be the $n$th flip. It is clearly unknowable in a heuristic sense. But it is also incomputable. Even by dumb luck, you couldn't write a computer program that would print out that string of 0s and 1s. (Of course this is with probability 1, but you could ignore that.)

2) A cardinality argument: If they know the difference between countable and uncountable (have they taken a math concepts course?) then explain that there are countably-many computable functions (countably many computer programs) and uncountably many functions.

Answer by Jason Rute for A function that is defined everywhere but has unknown values

2012-09-15T19:36:10Z

Kolmogorov Complexity

This should actually be easy to explain. Fix a programming language like Java. Let $K(n)$ be the length of the shortest computer program (in number of ASCII characters for example) that returns $n$ as the only output (in decimal notation for example). (This is roughly the Kolmogorov complexity of $n$.)

This is not computable (knowable) except for a few small $n$.

The main idea is that the even if we know a computer program that outputs $n$, there may be a shorter one. It just is taking so long to run, and the program itself uses such complicated math that we can't be sure it will stop and give $n$. (This can be made formal with the Halting problem or Gödel's incompleteness theorem.)

Note, this is a formalization of Barry's Paradox.

Consider the shortest number not definable in eleven words or less. We just defined it in eleven words.

We could also just use the paradox itself. Let $B(n)$ be the shortest number of English words needed to define $n$. Of course this isn't well-defined and leads to the above paradox.

Answer by Gerhard Paseman for A function that is defined everywhere but has unknown values

2012-09-15T20:00:10Z

It is not clear to me in what sense "known" is being used. A function I am interested in gives for input n the maximum determinant (over the reals) possible from the set of n-by-n matrices whose entries are either 0 or 1. It wasn't till a few years ago that f(14) was confirmed, even though its value was suspected for about half a century. There are other enumeration problems such as Dedekind's problem on monotonic Boolean functions for which only asymptotics are known. Perhaps a good definition of known could be provided by the poster.

Gerhard "There Is Also Jacobsthal's Function" Paseman, 2012.09.15