User gerard - MathOverflow

What is known about the area of the symmetric Pythagorean tree?

2013-05-03T20:52:57Z

What is known about the area of the symmetric Pythagorean tree? (Closed unit square as base, area of enclosed triangles not included.) The problem in calculating the area is that squares start to overlap from the sixth iteration onwards.

Without much effort it can be computed that height is 4 and breadth is 6, so an upper bound for the area is 24. Wikipedia reports that lower and upper bounds can with some effort be tightened to 5 and 18, respectively. The accompanying Wikipedia talk page reports on numerical approximations (pixel counts) that end somewhere near 14. Other than that, no trace of a hint of an exact answer in the literature.

Seems like a simple high-school problem. On closer inspection I believe it is not, due to the problem of overlapping squares.

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.

Comment by Gerard

2013-05-09T09:14:11Z

Why I do care? Because it is a challenging problem I am thinking about for a long while, got no further, and decided to share. Simple.

Comment by Gerard

2013-05-03T23:10:14Z

Okay, incorporated link.

Comment by Gerard

2013-05-03T22:26:24Z

"My guess". Wrong guess, do to neglect of overlap.

Comment by Gerard

2012-09-17T09:18:35Z

Thanks for slimming down the example. I took note.

Comment by Gerard

2012-09-17T07:27:30Z

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.

Comment by Gerard

2012-09-16T09:27:17Z

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 can use, so am more than satisfied.

Comment by Gerard

2012-09-15T16:07:04Z

Thanks. Example 1 is a real-word example, like my own Example 6. Point 2 is indeed treated later on in the course.

Comment by Gerard

2012-09-15T14:37:08Z

Well, how you've put your question is certainly a nice trick to generate much page views.

Comment by Gerard

2012-09-15T14:34:04Z

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.

Comment by Gerard

2012-09-14T23:44:42Z

Might be a solution but too involved for freshman computer science.

Comment by Gerard

2012-09-14T23:34:26Z

Still, this solution, notwithstanding that it excels for classroom use, still involves an argument that is linked to computability, which is something I'd rather like to avoid. (It is OK if you call me picky.)

Comment by Gerard

2012-09-14T23:23:18Z

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

Comment by Gerard

2012-09-14T23:17:40Z

You're right. Every constant function is computable. So my own example (3) does not qualify. I already complained that I am not satisfied with (3) because it is a constant function.

Comment by Gerard

2012-09-14T23:12:44Z

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.

Comment by Gerard

2012-09-14T23:10:52Z

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?