Wikipedia:Reference desk/Archives/Mathematics/2009 January 29

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.

January 29

Proven but not constructed

In mathematics, what objects if any have been proven to exist, but have not yet been constructed? NeonMerlin 06:20, 29 January 2009 (UTC)

Well, for example, we know an integer solution to Graham's problem exists, but the bounding limit is stupendously ginormous. For a different type of example, I suppose one could say that we know that uncountable real numbers exist (given the most frequently assumed axioms of mathematics) and yet by definition it would be impossible to explicitly enumerate one. Dragons flight (talk) 06:55, 29 January 2009 (UTC)

We know that uncountably many real numbers exist. Whatever do you mean by enumerating an uncountable real number? --Trovatore (talk) 08:00, 29 January 2009 (UTC)

Specifically, I mean construct an example of a number in the set of real numbers which can not be reached via a countable enumeration of the elements. But since one can always append your new example to any existing covering, that number is self-evidently countable. And yet at the same there are also uncountably many number you missed through any countable covering. We can attempt to enumerate the real numbers in any multitude of countable ways but no matter what your approach, the nature of the problem is such that one can never construct an example of a specific number that a counter would be incapable of saying. Dragons flight (talk) 08:28, 29 January 2009 (UTC)

Perhaps a clearer way to say it is that we can prove that even given infinite time someone picking numbers at random from the unit interval must omit uncountably many of them, and yet it is also impossible to construct any examples of numbers that a random chooser is guaranteed to miss. Dragons flight (talk) 08:42, 29 January 2009 (UTC)

There are no numbers that a random chooser is guaranteed to miss. --Trovatore (talk) 09:26, 29 January 2009 (UTC)

Yes, I know, that's the point. The question asked for things which are known to exist but have not been constructed. It is known that there exist numbers that a random chooser will miss and yet such number can not be constructed. Dragons flight (talk) 10:42, 29 January 2009 (UTC)

There are no numbers that a random chooser is guaranteed to miss, constructible or not. The chooser will miss most numbers, but which ones they are is entirely random; no numbers are off-limits. Algebraist 15:07, 29 January 2009 (UTC)

Hence, why it is impossible to construct one... I think you are both being pedantic to the point of being annoying. The whole point of this diversion was to try and give the poster an example of things which exist that can not be constructed. Dragons flight (talk) 18:10, 29 January 2009 (UTC)

But you didn't give such an example.

We aren't being pedantic. This is important. It's very common to throw around terms like "definable" and "constructible" without really saying what one means, and this leads to all kinds of trouble. There are whole careers dedicated to studying different sorts of definability and constructibility. --Trovatore (talk) 18:27, 29 January 2009 (UTC)

Well either A) you have a notion of "constructible" that allows you to construct specific examples of numbers that fail to be reachable after a countably infinite number of random selections. (Which I'm pretty sure you don't. Since that would appear to be impossible by definition.) Or B) you decide such numbers are "not constructible". Or C) you have a notion of "constructible" that provides that such examples would be neither "constructible" nor "not constructible", in which case I think your notion of "constructible" is sufficiently silly that I no longer care. Dragons flight (talk) 20:02, 29 January 2009 (UTC)

Maybe we're talking past each other; I'm not sure. In context, responding to the question asked, it sounded like you think the elements you have not enumerated have some different character ("cannot be constructed") from the ones that you have.

But they don't; you just stopped too soon. You can't enumerate the reals in countably many steps because there are just simply too many of them; that's really all there is to it. It's like taking a set with six elements, and noting that if you pick any five of them you'll always leave one out (which of course is true), and then phrasing that as "there's an element of the set that can't be enumerated in five steps", which is nonsense. --Trovatore (talk) 09:17, 30 January 2009 (UTC)

Let S be the subset of the unit interval containing those numbers which a random chooser is guaranteed to miss. You appear to be claiming that we can prove that S is nonempty, but we cannot construct any elements of S. However, this is not true, for S is certainly empty. I think you are conflating "the set of numbers which a random chooser is guaranteed to miss" with "the set of numbers which a random chooser happens to miss on one particular trial". Eric. 131.215.158.184 (talk) 23:33, 29 January 2009 (UTC)

One example might be, if we assume the axiom of choice, then there exists a well ordering of the real numbers. But we could never construct such a well ordering. Another example: again assuming the axiom of choice, we can prove the existence of a set with no Lebesgue measure. Eric. 131.215.158.184 (talk) 10:25, 29 January 2009 (UTC)

But does really the OP refer to existence proofs in mathematics that cannot be made constructive, like the various applications of the axiom of choice quoted above? Another popular one is Banach-Tarski paradox, whose utopistic constructive form is sometimes popularized as "how to double a golden ball". It seems to me that the OP refers rather to existence results that only later were given a constructive proof, or that are still demanding for it. In this direction, one example among many, is the envy-free partition in fair division problem: finding an algorithm was considered one of the big problems of the 20th century (well at least by the fair-division people). But the purely existence result is an immediate application of a Lyapunov convexity theorem in measure theory. In fact many other examples are in all math: of course it's commonly easier to prove that an equation has a solution, that exibite it concretely. As we know this fact is an eternal source of jokes on pure mathematicians --only physicists usually find them funny.pma (talk) 11:26, 29 January 2009 (UTC)

Ah, that's a good example, I wasn't aware of the history behind fair division. Here's another example, from a friend of mine, of something that cannot be made constructive: there exists an even number greater than 2, such that if the Goldbach conjecture holds for that number, then it holds for all numbers (the proof is by contradiction). But obviously we aren't going to construct such a number. A similar claim can be made for Fermat's Last Theorem, etc., etc. Eric. 131.215.158.184 (talk) 20:31, 29 January 2009 (UTC)

The busy beaver function Σ(n) has a definite (positive integer) value for all n but no values are known for n>4, it is non-computable, and it is not even possible to compute a bounding function. Gandalf61 (talk) 11:30, 29 January 2009 (UTC)

At probabilistic method there are some examples of graph classes known to exist but not yet constructed. A different type of example: there is a real number which is not the output (as a decimal string) of any Turing machine. We can describe it via a diagonalization argument but we can't actually find it. McKay (talk) 11:33, 29 January 2009 (UTC)

I will assume here that "construct" means "define." In that case, 131's comment needs to be qualified, because if the axiom of constructibility is true then there is a definable well-ordering on R (and indeed on the universe). So 131's statement needs to be clarified. Joeldl (talk) 12:06, 29 January 2009 (UTC)

There is no definition of a well-ordering on R provable in ZFC. — Emil J. 13:19, 29 January 2009 (UTC)

That's true — but that could simply mean that there is a definable formula that wellorders R, but that ZFC is too weak to prove it. I sort of doubt this is actually the case, but I'm not convinced we have enough evidence to firmly rule it out. --Trovatore (talk) 09:59, 3 February 2009 (UTC)

we often use the proof of a number we dont actually construct as part of a proof by contradiction. for example you can use it in the proof that there are uncountably many real numbers. the number so constructed was made as follows. if you could count all the all the real numbers between 0 and 1

1. 0.something
2. 0.something
3. 0.something
4. 0.something

...
then you could:

• express the something parts in binary
• if any of them terminates, pad it with endless zeros afterwards.
• define a new number, 0.somethingnew whose:
  • 1st binary digit is the opposite of the 1st digit of 1
  • 2nd binary digit is the oppose of the second digit in 2

and so on forever.

Now you have constructed a new number that differs from EVERY real number between 0 and 1 that you had enumerated. It's not one of them. But it is a real number number between 0 and 1. So, you didn't enumerate every real number in that space after all, however you thought you did. This is a contradiction. As you can see, it involves defining a number that we never construct. (Since we are working in the general case -- we didn't actually ask how you enumerated these reals, we showed that you can't no matter what you do -- we couldn't have constructed it: our proof didn't assume enough information). —Preceding unsigned comment added by 82.120.227.157 (talk) 14:51, 29 January 2009 (UTC)

My favourite example is in computational graph theory. It follows from the Robertson–Seymour theorem that for any class of graphs closed under minors, there is an algorithm (in fact a cubic-time algorithm) for determining whether a given graph lies in the class. But in almost all cases (e.g. the case of embeddability in a surface of genus k>1) we can't actually construct such an algorithm. Algebraist 15:05, 29 January 2009 (UTC)

How about the Riemann mapping theorem? Michael Hardy (talk) 16:57, 29 January 2009 (UTC)

Yes... but of course any construction problem is meaningful if the data are well definite and constructible objects; in this case, at least in case when the boundary is rectifiable, the problem has a variational structure (it minimizes the energy among all H¹ maps $u\scriptstyle :({\bar {D}},\partial D)\to ({\bar {\Omega }},\partial \Omega )$ whose restriction to the boundary is a parametrization), so it can be treated algorithmically via gradient flow -which is maybe not a great construction, ok...--pma (talk) 17:41, 29 January 2009 (UTC)

Some Number Theory

Studying an introductory number theory book, the following problem is given in the very beginning of the book. (Only the GCD, LCM, the division, and the Euclidean algorithm are known.) The problem states that let a and b be positive integers such that $(1+ab)|(a^{2}+b^{2})$. Show that the integer $(a^{2}+b^{2})/(1+ab)$ must be a perfect square. I have tried several techniques from earlier exercises but this is at the very end so I am guessing that this is supposed to be the hardest one and everything seems to fail. Any hints on how to get started? Thanks!-Looking for Wisdom and Insight! (talk) 09:58, 29 January 2009 (UTC)

As a starting point, if nothing leaps to mind, looking for numerical examples can be of help. After hunting around a bit I found that $b=a^{3}$ is always a solution (check it). However, there certainly exist other solutions, such as (8, 30), (27, 240), (30, 112), (64, 1020), (112, 418), (125, 3120), etc., so that's not the end of the story. Unfortunately nothing else came to mind for me; hopefully someone else has pointers. Eric. 131.215.158.184 (talk) 05:13, 30 January 2009 (UTC)

Consider the sequence of polynomials

$p_{0}=0$

$p_{1}=x$

$p_{2}=x^{3}$

$p_{3}=x^{5}-x$

$p_{4}=x^{7}-2x^{3}$

$p_{n}=x^{2}p_{n-1}-p_{n-2}$

Then

$p_{1}^{2}+p_{0}^{2}=x^{2}=x^{2}(p_{1}p_{0}+1)$

$p_{2}^{2}+p_{1}^{2}=x^{6}+x^{2}=x^{2}(p_{2}p_{1}+1)$

$p_{3}^{2}+p_{3}^{2}=x^{10}-x^{6}+x^{2}=x^{2}(p_{3}p_{2}+1)$

and we can prove by induction that

$p_{n}^{2}+p_{n-1}^{2}=x^{2}(p_{n}p_{n-1}+1)$

So if k is any integer greater than 1 then we can take a and b to be any two consecutive terms from the sequence $p_{n}(k)$ to get a solution to

$a^{2}+b^{2}=k^{2}(1+ab)$

For example, with k=2 we have the sequence 2, 8, 30, 112, 418, 1560, 5822 ... and with k=3 we get 3, 27, 240, 2133 ... This gives us a whole bunch of pairs (a,b) such that $(1+ab)|(a^{2}+b^{2})$, and, indeed, $(a^{2}+b^{2})/(1+ab)$ is a perfect square in each case. What I can't (yet) do is prove that these are the only solutions. Gandalf61 (talk) 12:27, 30 January 2009 (UTC)

Spoiler! I found the solution. The hunt for the solution was a bit of an adventure: The way I found this solution was using Gandalf's K=2 sequence and looking it up in the Online Encyclopedia of Integer Sequences (This is a great resource which has often helpped me by allowing me to brute force the first couple solutions of a problem and then find more information about that list of numbers) which gave me sequence A052530 which linked to sequence A061167 which contained the link to the St Andrews Colloquium. Anythingapplied (talk) 18:22, 30 January 2009 (UTC)

(edit coincidence) Very good. And you can start your method from any solution pair, and you can also go down, till you reach the solution (0,k), showing that the solution pair was indeed listed in your sequence (it is the same argument for the recently posed question on markov numbers). I made a search on your polynomials and I also found this: [1], where a discussion of this and other problems is given. --pma (talk) 18:25, 30 January 2009 (UTC)

May I ask how you searched for the polynomials? Google tends to not be great when trying to look up math equations since most symbols are reserved for other purposes. Did you use something else or is there a trick to it? Anythingapplied (talk) 18:47, 30 January 2009 (UTC)

I wish I knew such a trick... No, I started from Chebyshev polynomials and quadratic diophantine, untill I had the same idea as you and reached the link via the Sloane encyclopedia, directly from the k=2 sequence. It's very efficient, yes, you did well to remark it. IN fact it also works for a search of polynomials, using the finite sequence of coefficients. (NOte: I was asked exactly this problem like 10 years ago or so, and I solved on sight. In the last nights, I passed hours trying to remember something, and experienced a horrible sense of darkness!) pma (talk) 21:18, 30 January 2009 (UTC)

Awesome guys, thanks for all this info. No wonder I couldn't crack it. Even in the IMO it was a double starred problem.-Looking for Wisdom and Insight! (talk) 21:10, 31 January 2009 (UTC)

Sum of interior angles of polygons constant - proof?

It is well known that the sum of the interior angles of a triangle equals 180°, and (n-2)·180° for n-sided polygons. I've been unable to find a proof for that. If I had a proof for the sum of interior angles being constant, then the former can easily be deducted. I bet this is an easy one :) - Keta (talk) 19:03, 29 January 2009 (UTC)

The classic proof is in Euclid's Elements (online edition in English here), book I, proposition XXXII. Of course, it doesn't hold in non-Euclidean geometry, where the interior angles can sum up to less or more than 180°. -- Jao (talk) 19:27, 29 January 2009 (UTC)

That's the triangle case. Where does Euclid do the n-gon? I think he does it by cutting the n-gon into n-2 triangles, but I'm not sure. Algebraist 19:40, 29 January 2009 (UTC)

Yes. Corollary 4, just below. -- Jao (talk) 19:49, 29 January 2009 (UTC)

That only covers a special case, though. Does he prove the result for general n-gons? Algebraist 19:54, 29 January 2009 (UTC)

Ah, you mean the construction only works for convex polygons? That does seem to be a problem. -- Jao (talk) 20:04, 29 January 2009 (UTC)

Well, for polygons where one vertex can see all the others. That covers some but not all of the nonconvex case. Algebraist 20:07, 29 January 2009 (UTC)

After you've done the triangle, you can take care of the n-gon by mathematical induction: Every time you add a new side to the polygon, you add another 180 degrees. Or in other words, just triangulate the polygon and add up the angles in all the triangles. Michael Hardy (talk) 23:16, 29 January 2009 (UTC)

Yes, I was just wondering how Euclid proved that polygons can always be triangulated in this way. Algebraist 23:17, 29 January 2009 (UTC)

Thanks for the answers guys — fully satisfied with the info :) - Keta (talk) 21:59, 30 January 2009 (UTC)

Numerical error

Plot showing the numerical error

I am solving a dynamics problem using the Newmark method, and I am getting this strange numerical error (see figure on right) for some reason. For the parameters I am using, I should get a straight horizontal line as the solution, but I am getting these periodic pulses in the solution. The number of pulses does not depend on the total time for which I am doing the integration, but on the number of discretization points (1/Δt). What could be causing this problem? Any ideas would be highly appreciated. Please ask me if further information is needed to answer this question. Thanks! deeptrivia (talk) 22:38, 29 January 2009 (UTC)

Are you doing these calcs on computer ? If so, one thought is that, if Δt is too small, precision errors in the program may start to creep in, especially if the variables used are of low precision. StuRat (talk) 05:17, 30 January 2009 (UTC)

Does look a strange one. The more accurate finite difference methods tend to fall prey to numerical stability more often, but what usually happens is that the error grows exponentially going ping pong up and down. The error in yours does look like it is starting to grow exponentially each time, then it gets to a limit and reverses itself down, then after a while starts up again. Dmcq (talk) 12:08, 30 January 2009 (UTC)

sin(G)

Is there any way to estimate the sine of Graham's number (or has this been done)? It seems to me like it is too big a number to even be able to determine whether its sine is positive or negative, let alone calculate even a roughly accurate value for its sine. —Preceding unsigned comment added by 65.31.80.94 (talk) 23:14, 29 January 2009 (UTC)

I offer the strict (because G is rational) bounds -1 < sin(G) < 1. Anyone who wishes to strengthen this theorem is welcome to calculate the log₁₀(G) digits of π required to determine if it is positive or negative. Fredrik Johansson 10:28, 30 January 2009 (UTC)