7
$\begingroup$

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:

  1. 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.

  2. The busy beaver function. Also an uncomputable function. Which is a bit harder to explain.

  3. 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.

  4. 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.

  5. 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".)

  6. 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.

$\endgroup$
15
  • 5
    $\begingroup$ Consider $f(n)$ given by the first place where $\pi$ has a string of $n$ zeros in its decimal expansion. $\endgroup$ Sep 14, 2012 at 12:53
  • 15
    $\begingroup$ Consider the function that is 1 everywhere if at least one proposed example suits your tastes, and 0 everywhere if whichever suggestion comes you can always find some reason to reject it. $\endgroup$
    – johndoe
    Sep 14, 2012 at 13:06
  • 4
    $\begingroup$ Witty, but avoids the question. $\endgroup$
    – Gerard
    Sep 14, 2012 at 13:08
  • 4
    $\begingroup$ Your function (3) is computable! (I'm not saying I can compute values for you, but whatever function it happens to be -- the constant 0 or constant 1 -- is a computable function). So apparently your question does not rule out computable functions, in contradiction to your closing remark. $\endgroup$ Sep 14, 2012 at 20:10
  • 7
    $\begingroup$ I'm afraid I have to cast the last closing vote. You say in the last paragraph that your question rules out computable functions. And yet you accept as answer(s) functions which might, for all we know, be computable (if some conjecture is settled). The grounds for what is an acceptable answer seem to shift around, and some of the tone has been argumentative, and therefore I find the question "subjective and argumentative". $\endgroup$
    – Todd Trimble
    Sep 15, 2012 at 20:06

11 Answers 11

8
$\begingroup$

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$.

$\endgroup$
4
  • $\begingroup$ Very close in spirit. But then I want to know for sure that for enough $n$, the proposition $f(n)=1$ is unknown. I.e., I want to know for sure that for enough $n$ it is common knowledge that $f(n)$ is a proposition that lacks proof or disproof until now. (Like is the case with, e.g., Goldbach's conjecture.) How do I know? $\endgroup$
    – Gerard
    Sep 14, 2012 at 23:10
  • $\begingroup$ @Gerard, I believe in this case proof is lacking for all $n$ -- I think it's not known if the function that measures the gap between consecutive primes has any minimum in the limit (as you restrict to primes greater than $N$, with $N$ going to infinity). Hopefully someone who knows for sure what's known or not known will weigh in here. $\endgroup$ Sep 14, 2012 at 23:46
  • 2
    $\begingroup$ According to Wikipedia: Polignac's conjecture from 1849 states that for every positive even natural number k, there are infinitely many consecutive prime pairs p and p′ such that p′ − p = k (i.e. there are infinitely many prime gaps of size k). The case k = 2 is the twin prime conjecture. The conjecture has not been proved or disproved for any value of k. $\endgroup$
    – Tony Huynh
    Sep 15, 2012 at 10:37
  • $\begingroup$ With Polignac's conjecture I think I have found my example. My nr. 2 (with attractive demonstrative features) is Yoav Kallus' suggestion on Conway's Game of Life "halting problem". Joel David Hamkins'solution on true but principally unprovable statements seems for what I can see the most accurate but less suitable for classroom discussion. $\endgroup$
    – Gerard
    Sep 15, 2012 at 14:34
15
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thanks. I am not sure what to make of it, because I couldn't find out that quickly whether $R(m,n)$ is computable. If it isn't, then it is a valid example, but still a bit too much because it involves Ramsey numbers. $\endgroup$
    – Gerard
    Sep 14, 2012 at 13:42
  • 3
    $\begingroup$ Note, $R(n,m)$ is computable: We know it is finite and we even know upper bounds. Then search through the finitely many graphs of lower size. (It is even primitative recursive.) Hence this is an example of a function which in theory is computable, but in practice is not. $\endgroup$
    – Jason Rute
    Sep 14, 2012 at 17:08
  • 5
    $\begingroup$ The above "joke" is a famous comment made by Erdos on the above diagonal Ramsey numbers (somewhat loosely told). $\endgroup$ Sep 14, 2012 at 21:34
  • $\begingroup$ I don't understand why this answer on diagonal Ramsey numbers is upvoted so many times. Although function values are difficult to compute, the function itself is computable (cf. Remark Jason Rute). $\endgroup$
    – Gerard
    Sep 14, 2012 at 23:23
  • 2
    $\begingroup$ I am not exactly sure what you are looking for, but I would not be so quick to rule out computable functions. For example, let $f(n)=1$, if there are $n$ consecutive $7s$ in the decimal expansion of $\pi$, and otherwise $f(n)=0$. This is the function from Joel David Hamkins answer to the related question linked to in the comments. The point is that $f$ is clearly computable, but we do not really know most values of $f$ because we do not know which computable function $f$ is. Philosophically, I personally like Joel's answer best. $\endgroup$
    – Tony Huynh
    Sep 15, 2012 at 0:41
12
$\begingroup$

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$.

$\endgroup$
4
  • $\begingroup$ Thanks, your answer is specific. It gives a concrete example of a function of which the values are defined but cannot be known due to "gaps" in ZFC. However, I do not possesses the expertise to verify whether you answer is correct, let alone that students can do that. (Teachers should never underestimate their audience, but I think I am safe here.) So your answer does not meet my wish that it can be explained easily for pedagogic purposes. And, yes, there is a free lunch. (I.e., I do think that a simple example exists.) $\endgroup$
    – Gerard
    Sep 14, 2012 at 13:43
  • 2
    $\begingroup$ My thought was that provable independence provides a precise way to understand when we do not "know" the value of a function. Otherwise, I am afraid that I find the question vague... $\endgroup$ Sep 14, 2012 at 13:56
  • $\begingroup$ I have not credited your answer, not because I think it is wrong (in my first comment I indicated that I do not possess the expertise to see whether your answer is correct), but simply because it cannot be used in a course for bachelor students computer science. That's all. $\endgroup$
    – Gerard
    Sep 14, 2012 at 14:08
  • 1
    $\begingroup$ If one is looking at functions $f:\mathbb{N}\to \{0,1\}$, then one could make a similar but simpler example by $f(n)=1$ if the GCH holds at $\aleph_n$, that is, if $2^{\aleph_n}=\aleph_{n+1}$, and otherwise $f(n)=0$. This function is defined on all $n$, but the various values again are independent of ZFC and of each other in a very strong way. This function can be any desired function, if one goes to a forcing extension. $\endgroup$ Sep 15, 2012 at 11:48
10
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ I think the set of all finite subsets is the better choice for a domain here. For one, it is countable. But also, when your starting configurations extend out infinitely, there is no hope to begin with of computing their fate. $\endgroup$ Sep 14, 2012 at 14:44
  • $\begingroup$ Yoav, it is not a problem for me that $2^{\mathbb{Z}\times\mathbb{Z}}$ (or $2^{\mathbb{N}\times\mathbb{N}}$ for that matter) is uncountable. I just want to have a well-defined total function. $\endgroup$
    – Gerard
    Sep 14, 2012 at 14:51
  • $\begingroup$ I now realise that if I settle for an example function with an uncountable domain, the solution can no longer be regarded as member of $\mathbb{N}\to\mathbb{N}$, so violates the constraint of my original question. Guess I am back at my original question. $\endgroup$
    – Gerard
    Sep 14, 2012 at 18:44
  • 1
    $\begingroup$ As I said in my earlier comment, the initial configurations should be restricted to ones that extend only over a finite region. Such configurations are countable and the halting problem for them satisfies your criteria. $\endgroup$ Sep 14, 2012 at 19:07
  • 1
    $\begingroup$ The domain of Conway's Game of Life is the set of finite subsets of $\mathbb{Z} \times \mathbb{Z}$. $\endgroup$
    – Lee Mosher
    Sep 14, 2012 at 22:56
8
$\begingroup$

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).

$\endgroup$
3
  • 2
    $\begingroup$ GH, I think what the OP wants is a function whose values are unknown in principle, not just in practice. As with Ramsey Numbers (see Tony Huynh's answer), it's clear how to compute the largest prime factor of a Fermat number, I just wouldn't want to do so to a deadline. $\endgroup$ Sep 14, 2012 at 20:58
  • $\begingroup$ Same considerations as with Barry's solution: I want to know for sure that for enough $n$ it is common knowledge that $f(n)$ is a proposition that until now lacks proof or disproof. $\endgroup$
    – Gerard
    Sep 14, 2012 at 23:12
  • $\begingroup$ @Gerard: My "Added 1" example is subtle. It is known that $f(n)$ exists but we have no means to calculate it. This is connected to a certain kind of counterexample to the Generalized Riemann Hypothesis, called the Siegel zero. As for the "Added 2" example: it is conjectured that any integer not congruent to $\pm 4$ modulo $9$ is a sum of three integral cubes, but the conjecture is widely open. This example is simpler than Barry's. On the other hand, if the conjecture is true, then $f(n)$ can be calculated by trial and error, which is not the case with Barry's example. $\endgroup$
    – GH from MO
    Sep 15, 2012 at 12:42
4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ This (possibly partial) function is computable: generate decimal expansion of $\pi$ until you hit a string of $n$ fives. Else, absence of answer is permitted by definition of computable function. Values of computable functions on their domain of definition are known due to, e.g., dovetailing. I asked for existing but unknown values. $\endgroup$
    – Gerard
    Sep 14, 2012 at 13:14
  • $\begingroup$ No, if you admit partial functions, all your initial examples fails : to sove the halting problem for T(n), just run the Turing machine T(n) until it stops... $\endgroup$ Sep 14, 2012 at 13:44
  • $\begingroup$ The Halting function is a total function, i.e., it is defined everywhere on $\mathbb{N}$. It is $1$ when (inputless) $T(n)$ stops and $0$ when (inputless) $T(n)$ does not stop. $\endgroup$
    – Gerard
    Sep 14, 2012 at 13:53
  • $\begingroup$ So what have you got against the "partial" halting function : 1 if T(n) stops and not defined if it doesn't stop. With your vison of those things, that one would be computable, right ? And there is an even more interesting similar function : f(n) = number of steps before halting (and no answer if no halting)... which prevents the arguing about the lack of interest of the values of the function $\endgroup$ Sep 14, 2012 at 14:01
  • $\begingroup$ Thanks. I have nothing against the partial halting function ($1$ when $T(n)$ stops, undefined otherwise), except that is, for all I know, computable, hence uninteresting in as far my question is concerned. $\endgroup$
    – Gerard
    Sep 14, 2012 at 14:20
2
$\begingroup$

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. :) ]

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks. Example 1 is a real-word example, like my own Example 6. Point 2 is indeed treated later on in the course. $\endgroup$
    – Gerard
    Sep 15, 2012 at 16:07
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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").

$\endgroup$
1
  • $\begingroup$ Might be a solution but too involved for freshman computer science. $\endgroup$
    – Gerard
    Sep 14, 2012 at 23:44
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I've just closed the question anyway, Gerhard. What the OP is after doesn't seem all that clear, as you point out. $\endgroup$
    – Todd Trimble
    Sep 15, 2012 at 20:08
  • $\begingroup$ Fair enough. I agree we (I) began to move to shaky grounds, which led to all kinds of suggestions. Nevertheless, I spotted an answer I think can use, so am more than satisfied. $\endgroup$
    – Gerard
    Sep 17, 2012 at 7:27

Not the answer you're looking for? Browse other questions tagged or ask your own question.