Wikipedia:Reference desk/Archives/Mathematics/2015 March 19

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

March 19

Interesting number paradox question

I was reading the article on the Interesting number paradox. It says that there are no uninteresting numbers because if there were uninteresting numbers we could put them in a set: a set of all non-interesting numbers. If we ordered all the numbers in that set there would be a smallest non-interesting number; that number would be interesting. But by being interesting that number creates a contradiction that invalidates the premise that there are no uninteresting numbers.

I understand that but what if the set of uninteresting numbers was a countable infinite set? In this case there would not be a smallest item in the set and hence there are uninteresting numbers. How does this paradox relate to sets with counably infinite size? Thanks for reading! meshach (talk) 05:30, 19 March 2015 (UTC)

The paradox deals with Natural numbers. The natural numbers are Well-ordered, meaning that every nonempty set of natural numbers has a smallest number. The set of uninteresting numbers has a smallest number, even if the set is infinite.

Of course, the paradox shouldn't be taken too seriously, since "interesting number" is not defined, and the claim that the smallest uninteresting number is interesting is arbitrary. -- Meni Rosenfeld (talk) 07:38, 19 March 2015 (UTC)

Now that you explain the concept of Well-order - I had never read that page and I did not know about that property of sets - I see how there must be a smallest number in the set. Thanks for replying! Also I know that this question does not have a practical side, it was more of a curiosity on my part. meshach (talk) 16:11, 19 March 2015 (UTC)

Natural numbers set is countably infinite and obviously there is a smallest one among them... --CiaPan (talk) 08:16, 19 March 2015 (UTC)

Note also that all numbers are small, because most numbers are bigger. Bo Jacoby (talk) 09:27, 19 March 2015 (UTC).

Modern mathematics posits the existence of supernatural beings that are able to gather together infinitely many numbers satisfying some property. How typical of us humans to think that it is the interestingness of the numbers that is paradoxical in this setting. It's like saying: suppose I have an infinite number of monkeys in my apartment. Isn't it strange that some monkey must eventually type out the entirety of the play Hamlet? No thought is given to the strangeness of having infinitely many monkeys in the first place. Sławomir Biały (talk) 11:41, 19 March 2015 (UTC)

The really interesting question tough, is if you have infinitely many Wikipedia editors in your appartment... YohanN7 (talk) 13:42, 19 March 2015 (UTC)

Consider the play Hamlet written as k characters from an alphabet consisting of, say, 64 characters. Let N=64^k. Write some irrational number, say π , in base N, meaning that there are N different digit values, 0 1 2 . . . N−1. Among the first N² digits each digit value occurs about N times. So with overwhelming certainty the entirety of Hamlet occurs at least once. And no infinity is needed, only N² base N digits. Bo Jacoby (talk) 18:40, 19 March 2015 (UTC).

I don't see how that would work. The base N digits of π are not random. Sławomir Biały (talk) 21:33, 19 March 2015 (UTC)

π is thought to be a normal number, but nobody has actually proved that. The closest result that I know is that, with some reasonable sounding assumptions, it is normal in base-2. Abecedare (talk) 22:03, 19 March 2015 (UTC)

Of course, even if π is normal, its digits are not random. But they behave like random digits for the purposes of Bo's argument. -- Meni Rosenfeld (talk) 22:17, 19 March 2015 (UTC)

"But they behave like random digits for the purposes of Bo's argument." What is the basis for this statement, I wonder? Sławomir Biały (talk) 23:17, 19 March 2015 (UTC)

It follows from the definition of normal numbers. Also note that being normal in base-2 implies being normal in base-$2^{m}$, so the above linked paper suffices for Bo's argument (assuming you accept its Hypothesis A). Of course, Bo could have bypassed all this by simply saying "write some number, picked at random" instead of "write some irrational number, say π" and would have been almost surely right. Abecedare (talk) 23:26, 19 March 2015 (UTC)

Yes, but that just raises the question of how one "picks a real number at random"? Has a random real number ever been exhibited? Sławomir Biały (talk) 23:44, 19 March 2015 (UTC)

If I recall correctly, the various approaches to interpreting that question (and probability, in general) have been previously discussed at this desk; perhaps someone can locate the archive link. Don't believe that question is really relevant to this particular thread, so I'll desist from entering into that debate here. Abecedare (talk) 00:00, 20 March 2015 (UTC)

"Random" is a property of a process to choose a real number, not of a number itself. A real number can't be random any more than "9" is random. Talking about properties of random real numbers is really talking about measures of specific sets of numbers. When we say "a uniformly randomly chosen real number between 0 and 1 almost surely has ASCII-encoded Hamlet in its binary digits" is really saying "the set of real numbers between 0 and 1 which contain Hamlet has measure 1" - a claim that should be easily provable.

Similarly, if I'm not mistaken, a randomly chosen real number is almost surely normal. -- Meni Rosenfeld (talk) 13:33, 20 March 2015 (UTC)

Well, yes, I'm aware that randomness is a property of the process of choosing rather than the number. But it is said that "a random real number will contain Hamlet". The failure to be able to exhibit any random real number is certainly a deficiency of that response. What good is it to say that "an X has property Y" if one cannot even exhibit an "X"? Tell me how to "pick a real number uniformly at random between 0 and 1". Sławomir Biały (talk) 13:59, 20 March 2015 (UTC)

Any number with an N digit binary expansion can be randomly selected by flipping a coin N times and sequentially writing down the heads as 1 and the tails as 0 in a string like: 0.101101110100101000101010101, etc. Almost anything that can be said about random real numbers can also be said about sufficiently long random numbers generated by a process like that. As other parts of the discussion have said, after a certain number of binary digits it becomes almost certain that Hamlet is present, and we can certainly imagine processes to generate any finite number of random digits. Dragons flight (talk) 19:49, 20 March 2015 (UTC)

Yes, well there are really several issues here. One is that the notion of a random real number requires that we imagine carrying this process"to infinity". But one might (rightly) question whether such an operation is meaningful. Another is that no one actually believes that it is possible to generate the text of Hamlet by tossing a coin. It is not even clear that there should be enough free energy in the universe to achieve this, and if there were, it would probably be a very significant discovery. Not all problems of "infinite monkeys" are solved by replacing the infinity of monkeys by some inconceivably large number of monkeys, that would overfill the observable universe by tens of thousands of orders of magnitude. Now, the real Platonists would say that these mathematical abstractions do not exist in-the-world. Instead, they exist in an idea-space. My point is, mathematicians take for granted that such things are well-defined, even though they require faith in some supernatural interpretation to make proper sense of them. Cramming infinitely many monkeys into my apartment is just a colorful way to illustrate the absurdity of such ideas. Sławomir Biały (talk) 20:21, 20 March 2015 (UTC)

Sorry, I think I didn't correctly parse Meni's post. Obviously, if we assume that pi is normal, then pi is normal. But that begs the question. Is finding Hamlet in pi even likely to be decidable? Sławomir Biały (talk) 01:05, 20 March 2015 (UTC)

Well, sure. Just scan pi until you find Hamlet (which you almost definitely will, for a sufficiently abstract value of "you"). --Trovatore (talk) 01:11, 20 March 2015 (UTC)

But if Hamlet never occurs, then what? (I should be clear, I am not assuming that pi is normal. That begs the question, and I don't really find the paper linked above very convincing evidence that we ought to believe that pi is normal.) Sławomir Biały (talk) 11:22, 20 March 2015 (UTC)

Well, you asked about whether it is likely. If hamlet appears in π (as most people believe), then there is a proof of it, and hence this question is decidable. Hence, the question is likely to be decidable. -- Meni Rosenfeld (talk) 13:16, 20 March 2015 (UTC)

Ok, so the word "likely" invites misinterpretation. But this is all just arguing semantics. There isn't any non-question-begging reason to think that the digits of pi will contain Hamlet. Abecedare pointed to a paper where this is reduced to some mysterious Hypothesis A, which I'm not sure is reasonable either. Anyway, regardless of these issues, we're talking about a proposition that cannot ever be checked. Yet mathematicians still insist that it is "likely to be true" that if an impossibly large number of digits of π were written down, somewhere would be the text of Hamlet. So what is proposed does not seem so different from "infinite monkeys" to me. Sławomir Biały (talk) 13:54, 20 March 2015 (UTC)

Oh, I disagree entirely that there isn't any reason to think the digits will contain Hamlet. To put it mildly, if they didn't, the thing would need explanation. The decimal expansion of π has no reason to avoid Hamlet. I think it would be utterly freaking astonishing if the text of Hamlet did not occur. --Trovatore (talk) 14:20, 20 March 2015 (UTC)

Well, to my knowledge, it has not occurred. Yet no one is astonished by this. Sławomir Biały (talk) 14:39, 20 March 2015 (UTC)

Of course not. Because we haven't gotten anywhere near the number of digits you'd expect to need. --Trovatore (talk) 14:50, 20 March 2015 (UTC)

Right. So, in what year will it be appropriate to express astonishment at the lack of Hamlet appearing 8 the digits of pi? Sławomir Biały (talk) 14:57, 20 March 2015 (UTC)

If there were a reliable oracle that told us it did not appear, but did not give more information, it would be astonishing, and would justify a research effort to figure out why. --Trovatore (talk) 15:08, 20 March 2015 (UTC)

Indeed. But the existence of such an oracle would be even more astonishing. (And how we could certify that oracle as reliable?) Sławomir Biały (talk) 15:16, 20 March 2015 (UTC)

That isn't the point. --Trovatore (talk) 15:31, 20 March 2015 (UTC)

Isn't it? I started this sub thread with a tongue in cheek observation that modern mathematics routinely makes ridiculous statements, like "infinite monkeys" or gathering together infinitely many things into a collection. Oracles with access to infinitely many digits of pi do not seem immune to this criticism. Sławomir Biały (talk) 15:51, 20 March 2015 (UTC)

From my point of view, the sub-thread started with you wondering if the question was "decidable". Skipping my usual rant about the dual meaning of that word (independence from a formal theory vs a decision problem), in any ordinary sense, it's obviously decidable if it's true, and it's (almost) obviously true. Now, if you want to ask about it in some ultrafinitist interpretation, that's another matter altogether. --Trovatore (talk) 00:44, 21 March 2015 (UTC)

My copy of Shakespear's Hamlet is 44 pages of 2 columns of 61 lines of 51 characters of 6 bits, so k = 1642608 bits and N = 2^1642608 and among the first N³ = 2^4927824 bits of π Hamlet is found about N times. But presently only the first 2⁴⁵ bits of π are known. The requirement that π is normal is sufficient, but by no means necessary, for the probabalistic argument to be valid. Bo Jacoby (talk) 19:20, 20 March 2015 (UTC).

But the digits of pi are not random. It's perfectly conceivable (though I admit not very likely) that God could have made the mathematical world so that the digits of pi avoid the text of Hamlet. Or, what seems more likely, that there us some structure to the digits of pi that only becomes apparent after some inconceivably large number of digits have been written down. To tie this in with the subject of the thread, define the set of interesting real numbers to be all real numbers that can be uniquely characterized by finite sentences. The set of interesting numbers is countable, so has measure zero. Now take the complement of that set. So almost surely, a real number is not interesting. A probabilistic argument would lead us to the wrong conclusion that pi is almost surely not interesting. The problem is, pi was not "chosen at random" any more than a number like 3 is. Sławomir Biały (talk) 20:38, 20 March 2015 (UTC)

If interestingness is recursive then you don't need a completed infinity. You just need to check Interesting(0), Interesting(1), ... until one tests false. If interestingness is not recursive then you may have a point. -- BenRG (talk) 23:25, 19 March 2015 (UTC)

The "Interesting Number Paradox" is not a mathematical paradox because the word "Interesting" cannot be defined mathematically. It is a linguistic paradox. 175.45.116.65 (talk) 00:07, 20 March 2015 (UTC)

Well, I don't agree necessarily that "interesting" cannot be defined mathematically. A number can be "interesting" if it satisfies some predicate P(n) that is not satisfied by any other number. Now, that will clearly depend on what predicates there are. Naively, at least, any number should be interesting because it is either zero or the successor of its predecessor. But it seems to me that converting this to a unique predicate requires being able to obtain a unique formula of the form n = SS...S(0) in the meta-language (though of course, "many" numbers will be "interesting" for other reasons). Whether that is possible might just depend on the rules that are available. Interestingness (as defined here) is not be a first order predicate, so not inductive under the axiom schema of Pressburger arithmetic, although it seems possible that one might be able to prove it is inductive anyway. (But we have some real experts here about these kinds of things; I'm just an amateur.) Sławomir Biały (talk) 13:07, 20 March 2015 (UTC)

A Seemingly Simple Problem...

Given b, c in (0, 1) find a so that c = (a^b - 1) / (a - 1). I don't need an exact solution, and for a lot of values, it's simple to solve using numerical methods - however, some values of b and c seem to require a be exactly accurate (as in, trying all a from 0 to 1 in increments of 0.00000001, still gives a best solution being off from c by 0.2, which is high). Any advice on how to proceed would be extremely helpful - especially in the context of how to get a reasonably close value to a for a computer. Thank you for any help:-)Phoenixia1177 (talk) 17:49, 19 March 2015 (UTC)

Looking at the graph (note: x and y used respectively for a and b to avoid confusing the engine), it would seem that for 0 ≤ c < b ≤ 1, a might become exceedingly large. The graph seems to be very benign (insensitive to variations in a), so that the need for exact accuracy is not likely to be a problem (but computational error may become a problem), except in the steeper section where c quite a bit larger than b (the region where a is very small). Have you identified which of these regions is giving you the problem? They might need fairly different approaches to solve numerically. —Quondum 19:04, 19 March 2015 (UTC)

You'll need a better numerical method than "trying all a in increments", for example, the secant method. You might also need arbitrary precision arithmetic, rather than standard floating point. It's possible the numerical robustness will be better if you work with the log of c rather than c itself.

If you can give an example for problem values of b and c, I can see what my silicon overlord has to say about it. -- Meni Rosenfeld (talk) 19:09, 19 March 2015 (UTC)

Oddly, when a is large, Newton's Method almost always seems to get a solution extremely quickly, my problem is with various areas where a ends up something like (z-1)^²/z² with z = 1.0000000000001, and any less 0's in the z gives a number that is off (or causes Newton's method to veer off). I keep encountering things of this nature around b = 1/1000 and c = 1/4(ish), or round abouts. There's also a few weird cases where a is close to 0.98 that a difference of quadrillioniths starts to cause issues. I get the feeling that for certain b and c with a close to 1 that rounding errors, narrow intervals of convergence, and etc. are causing solutions to be very difficult to find. The problem is that, really, I only need to consider b's and c's that are multiples of 1 / 1000, or even 1 / 500, but even at that coarseness issues creep in. These have been my main difficulties so far, but I've only done dedicated testing up to hitting this wall - so largeness of a may become a problem, but basic testing seems to indicate it is manageable (especially if the numbers only go so fine, there's bound to be an upperlimit that is reasonable). Finally, the hardest difficulty I'm having is that problem values of b and c do not always seem to be around each other (a range of numbers works fine, something goofy is encountered, a range immediately after it works fine...which is weird, because the function isn't doing anything unusual to justify that).Phoenixia1177 (talk) 19:26, 19 March 2015 (UTC)

Having said of all that, I don't need to use this particular function, it's just the best that I could find for my purpose (but is appearing not to be such). Any family of functions 0 to 1 that are increasing and have the property that if rotated around the line 0 to 1 would appear to nicely curve out, then back in (I'm not good at this area of mathematics, I'm not sure what this is called, hopefully that makes sense), would work. Ideally, they'd be fairly simple functions involving parameters (like a above) that could be calculated to fit the specific case (the problem here). Unfortunately, I can't think of any alternatives that would be tractable to work with.Phoenixia1177 (talk) 19:26, 19 March 2015 (UTC)

A specific value is (b, c) = (0.00390625, 0.2421875) - going in steps of 1/10000000 from 0 to 2, the best I can do is get an a that gets to within 0.18 of c. (Householder style methods just seem to converge to something useless, or end up complex).Phoenixia1177 (talk) 19:26, 19 March 2015 (UTC)

Playing around with a calculator, the answer is, apparently, close to 1.00E-031 - iterative methods seemed to suggest something bigger should be the case. I'm thinking that perhaps I can use some sort of binary search to quickly zone in on where values should be, then focus in from there - it's a bit of a pain that this has such an extreme range of values...Thank you for the help:-) If anyone has any suggestions, or advice, I'd love a better approach:-)Phoenixia1177 (talk) 19:57, 19 March 2015 (UTC)

For any given value of b, the graph of c as a function of a appears to be monotonic. The particular case you are trying here is in an extremely steep portion of the curve, with a being very close to 0. Under these conditions, as a first approximation you can treat the denominator as −1, then solve directly for a. In this region, a ≈ (1 − c)^1/b. For the values you've given, a ≈ 1.47167442365×10⁻³¹. Iterative methods that suggest otherwise might be coded incorrectly? —Quondum 20:23, 19 March 2015 (UTC)

Thank you:-) I went ahead a used the binary search idea, it grabs the correct answer really fast to within 0.00000001 except for when b is very close to 0 or 1, in which case I have to make a few adjustments, but it works out. Thank you for all of your help, this has been bugging me all morning (and was supposed to be the "easy part" of what I was working on, the hard part has been done since lunch...as usual):-) The iterative methods seem to muck up because of some kind of rounding issue, which mimics looking like something should be there, but isn't - looking at the graph you linked helped out immensely (I have no head for this part of mathematics).Phoenixia1177 (talk) 20:57, 19 March 2015 (UTC)

I get

a= 1.471674423653163208979791381232519779312019651757196305407014996658...
...54737822741579826361275221008550373823931842344014924813903853384398...
...52350065926179168749115739190846671369912679492772146563629375676839...
...85255281110453825251379625625822121155663967952739575017888933730537...
...76412371176198447385083025894391324710480542924475543517834796969025...
...30898171178140142520846614909449876078873493159339572138400750026087...
...78889207319666634111295848971226524071453846595121566051527566088718 E-31

And there's plenty of more digits of precision where that came from.

You have to work with higher precision with sensitive functions. Standard floating point isn't going to cut it.

Additionally, methods which converge faster tend to be less robust to pathologies in the function. Binary search is very robust for monotonic functions, but will not zero in quickly on the exact value. You can begin with binary search to get the general area, and then move on to the secant method (it should be more robust than Newton's). -- Meni Rosenfeld (talk) 22:12, 19 March 2015 (UTC)

Measure of a particular projection

Fix infinite $P\subseteq \mathbb {N}$, and let $P=\{p_{0}<p_{1}<p_{2}\dots \}$ list the elements in order. Define $\pi _{P}$ a map from the unit interval to itself as follows: on input $r$, write the full binary expansion $r=b_{0}b_{1}b_{2}\dots$ and let $\pi _{P}(r)$ be the real number with binary expansion $b_{p_{0}}b_{p_{1}}b_{p_{2}}\dots$. Basically, we're throwing away all the bits in positions that don't correspond to elements of $P$. I'm aware there's some ambiguity for diadic rationals, but a set of measure zero won't matter for this question.

For reals $0<a<b<1$, I'm interested in the measure of $\pi _{P}([a,b])$. If there is a real $q$ and constant $c$ such that $|qn-|P\cap \{0,\dots ,n-1\}||<c$ for all $n$, then I can show that $\pi _{P}([a,b])<d(b-a)^{q}$, for a constant $d$ that does not depend on $a$ and $b$. It seems like this should hold in the more general situation $\lim _{n}{\frac {|P\cap \{0,\dots ,n-1\}|}{n}}=q$. Any thoughts?--80.109.80.31 (talk) 19:20, 19 March 2015 (UTC)

Shadow of an n-cube in n-1 along vertex first axis?

The 2-D shadow of a 3-cube along the axis from one corner to the opposite corner is a hexagon, the 3-D shadow of 4-cube along a corner to opposite corner axis is an Octahedron (aka 3-Orthoplex). For an n-cube where n is even, the shadow and the halfway slice would be the same, I believe, but I'm not sure where n is odd (where you aren't slicing through vertices. Any ideas on the odd?Naraht (talk) 19:42, 19 March 2015 (UTC)

I'm pretty sure that the projection of the 4-cube along a diagonal is the rhombic dodecahedron, not the octahedron. I haven't worked out higher dimensions, but you've got two more or less unrelated processes so it would be surprising if they led to the same result except by coincidence. For n=3 you can explain it by the fact that regular polygons are self-dual, but this doesn't hold in general. --RDBury (talk) 06:08, 20 March 2015 (UTC)

Why the Rhombic Dodecahedron? For the halfway slice of the hypercube (+-1,+-1,+-1,+-1) crossing the w=x=y=z axis, the 6 points farthest from the axis are the 6 permutations of (+1,+1,-1,-1) right? What would be the other 6 corners?

Scale the cube to (±2, ±2, ±2, ±2) to avoid fractions. Projected onto the plain x+y+z+w=1, these points are (0, 0, 0, 0) (twice), (3, -1, -1, -1) and permutations (four points), (2, 2, -2, -2) and permutations (six points), and (1, 1, 1, -3) and permutations (four points). (0, 0, 0, 0) is in the interior so it can be ignored. The vertices (2, 2, -2, -2) and permutations are bounded by the planes -2≤x,y,z,w≤2; these are the eight faces of the octahedron. But the remaining 8 points don't satisfy these inequalities and so are not within the octahedron. These are the 8 vertices of a cube, with each point being just above one face of the octahedron. The 6 outer vertices are distance 4 from the center and the 8 other vertices are distance √12 from the center, so these are not the farthest from the origin, but they are vertices since they are further from the origin than the centers of the triangle that form the octahedron. These centers have coordinates, up to permutation, (2, -2/3, -2/3, -2/3) and (-2, 2/3, 2/3, 2/3), making their distance from the origin 4/√3 which is less than √12. One face of the projection is x-y≤4 with the other faces obtained by changing variables, making 12 faces in total. The plane x-y=4 has four vertices (2, -2, 2, -2), (2, -2, -2, 2), (1, -3, 1, 1), (3, -1, -1, -1) which form a rhombus, so the polyhedron is bounded by 12 rhombi. --RDBury (talk) 18:09, 20 March 2015 (UTC)

For a cube, the shadow and the half-way slice are both hexagons, but they're not the same size. Maproom (talk) 20:31, 20 March 2015 (UTC)