Wikipedia:Reference desk/Archives/Mathematics/2007 February 27

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.

February 27

Proofs and computerized searches

The question above about Goldbach's conjecture got me wondering. It seems there are a number of famous conjectures or unproven theorems which have been subjected to brute-force searches for counterexamples. For example, the Goldbach article says it has been verified for n up to around 10¹⁷. I imagine Fermat's Last Theorem received similar attention. A layman like me might be tempted to think that a search to high numbers like that makes it a pretty good bet that any further searching is likely to be unsuccessful. My question is, have any of these large-scale searches simply not gone high enough, and a solution was later found by other means? Are there any interesting mathematical relationships that only kick in for enormous values? --TotoBaggins 00:30, 27 February 2007 (UTC)

A famous historical example is Pierre de Fermat's conjecture that all numbers of the form $2^{2^{n}}+1$ are prime (see Fermat number). This is true for the first several examples, but later Euler showed that $2^{2^{5}}+1=4294967297$ could be factored as $641\times 6700417$, an amazing achievement in 1732. The next 16 Fermat numbers are also known to be composite. So this was a conjecture that proved false only for "enormous" values larger than 4294967296—not so enormous by today's standards, but 300 years ago it was astronomical. —Bkell (talk) 01:47, 27 February 2007 (UTC)

Note that most large-scale computerized searches are not run indiscriminately. Usually, "regions of the search space" (whatever that means in context) that are likely to be "interesting" are targetted. The fact that some conjecture holds for large cases that were considered in some sense likely to be problematic is often more satisfactory evidence than just the number of cases where it holds. Phils 02:31, 27 February 2007 (UTC)

This is before computers, but π(x) − Li(x) < 0 for all non-enormous (<10³¹⁶ or so) values of x, so quite possibly people believed it to be negative for all x until Littlewood proved otherwise (see Skewes' number) Algebraist 15:34, 27 February 2007 (UTC)

Good answers, thanks! --TotoBaggins 16:27, 27 February 2007 (UTC)

Also note that often one can create a computer proof by attempting to reduce the number of cases that may need to be checked to some finite number, then checking each of these cases by computer (which is fast).

It may be the case that the bounding result may be found some time later than a computer search for counterexamples, so then the bounding result essentially will establish the proof.

The next sequence

0.6180339887498949 (0.5 - 1*x + 0.5 * x^2)

0.5436890126920763 (0.5 - 1*x + 0.5 * x^3)

0.5187900636758842 (0.5 - 1*x + 0.5 * x^4)

0.5086603916420042

0.5041382583616553

0.5020170551781655

0.5009941779228898

Is there a way of getting the next sequence with the tedious effort of solving the polynomial? 202.168.50.40 02:07, 27 February 2007 (UTC)

If the polynomials are supposed to have the values to the left of them as zeroes, then the higher exponents are one off. The n-th number above is a root of the equation x + ... + xⁿ⁺¹ = 1, which is equivalent to 1 – 2x + xⁿ⁺² = 0.

For larger values of n, a way to compute these values is to start with x = 0.5, and replace x iteratively by (1 + xⁿ⁺²) / 2 until convergence. While less efficient than, for example, Newton-Raphson, the formula makes up for that in simplicity.

Another way to reduce the tedium is to delegate the computations to an automatic computer.  --Lambiam^Talk 08:24, 27 February 2007 (UTC)

And, for a rough approximation, we can notice that each term is about half as far from 0.5 as the previous term, with this relationship becoming closer with each term. Thus, we can guesstimate 0.5005 for the next term. If anyone actually solves this, please let me know how close my guesstimate came. StuRat 15:36, 27 February 2007 (UTC)

To a first approximation the n-th term equals 0.5 + 0.5ⁿ⁺³, so indeed the distance to 0.5 is roughly halved each step. The next approximation is 0.5 + 0.5ⁿ⁺³ + (n+2)×0.5²ⁿ⁺⁵, which will give you already 10 accurate decimals for n = 12. If you want to play with this, here are a few more terms to a higher precision:

 1 0.61803 39887 49894 84820 45868 34365 63811 77203 09179 80576

 2 0.54368 90126 92076 36157 08559 71801 74798 65252 03297 65098

 3 0.51879 00636 75884 22190 74538 94435 27999 88621 27809 04685

 4 0.50866 03916 42004 13646 38429 65898 41399 53244 06435 90103

 5 0.50413 82583 61655 36083 05214 03975 64928 33803 90951 87446

 6 0.50201 70551 78165 51178 05402 77860 49131 76280 09418 58461

 7 0.50099 41779 22889 83685 40843 19392 13416 42444 63056 32758

 8 0.50049 31182 86552 25605 92684 59994 20216 15720 28613 43888

 9 0.50024 54622 66794 48360 09641 13516 38045 59668 32970 76331

10 0.50012 24294 76043 26230 25101 69147 80621 05651 44971 34601

11 0.50006 11322 39058 19052 95721 38910 20517 82711 64584 78650

12 0.50003 05436 87833 37599 15252 35986 50121 37831 40657 98461

13 0.50001 52657 78675 10503 21704 66776 06039 28968 51323 26731

14 0.50000 76312 57844 59185 97067 96078 38295 32638 05704 89164

15 0.50000 38151 92125 13295 17530 07820 32593 67421 30833 67851

16 0.50000 19074 79613 29054 37344 11929 52414 93738 71876 24039

17 0.50000 09537 08879 05077 94593 43474 95695 11574 63285 05994

18 0.50000 04768 46253 40602 29374 43191 17511 31062 13753 10999

19 0.50000 02384 20966 56044 60504 21229 97561 26017 52605 83145

20 0.50000 01192 09914 83323 37916 68920 35046 84045 98586 79104

 --Lambiam^Talk 17:11, 27 February 2007 (UTC)

This would drive you nuts

Jane Smith picks up her husband everyday at exactly 6pm at the local train station. One day her husband John Smith arrived back early at 5pm. Rather than waiting an hour for his wife, he started walking back at a constant speed of 4 km/hour. Jane Smith, departed from her house at the usual time and met her husband on the road. He got into the car and she drove home and arrives back at the house 20 minutes earlier than normal.

What is Jane Smith driving speed? For this problem you must assume that Jane Smith drives at a constant speed all the time, there is no traffic on the road and there is no traffic light on the road.

Good Luck! 202.168.50.40 02:17, 27 February 2007 (UTC)

Thanks, but this is not a forum for sharing puzzles. Look elsewhere on the net if you wish to find a more appropriate place to post. --KSmrq^T 02:39, 27 February 2007 (UTC)

I probably messed up, but doing it in my head, she was driving 80 km/hr. Nevermind, that can't be right, cause I didn't use calculus, which is more or less needed in this problem. --Wirbelwindヴィルヴェルヴィント (talk) 03:07, 27 February 2007 (UTC)

This is classic puzzle. Here's how to approach it. Since Jane arrives home 20 minutes earlier than usual, she must have been 10 minutes drive time from the station when she met John. So what time did she meet John ? So how long has John been walking ? Now suppose John has walked a distance X from the station in this time. Jane can drive this same distance X in 10 minutes. So how many times faster is Jane's driving speed than John's walking speed ? And you know John's walking speed, so Jane's driving speed is ... Gandalf61 10:08, 27 February 2007 (UTC)

A measure of non-concentricity - a unit or discriptor

I'm trying to find out how to describe circular objects that are supposed to be concentric, but are not quite. How does one describe non-concentricity? What would the unit of measure be? Thanks, (4crates 05:58, 27 February 2007 (UTC))

What is appropriate as a measure depends on the purpose and context. Should the measure be scale-independent — that is, if you blow everything up by the same factor, should the outcome remain the same? Or should it follow the scale?

A simple scale-dependent measure is the distance d between the centres of the circles. A value of 0 means perfect concentricity. For physical objects, this measure has the dimension of length. One possible scale-independent measure is d / r, where r is the radius of the smaller circle. If this measure is at most 1, the centre of the larger object is inside the smaller object. Another scale-independent measure is d / (R – r), where R is the radius of the larger circle. This assumes that R > r. If this measure is at most 1, the smaller object is fully inside the larger one. These scale-independent measures are dimensionless.  --Lambiam^Talk 08:34, 27 February 2007 (UTC) (edited 17:21, 27 February 2007 (UTC))

The general area of finding appropriate descriptions for quantities like this is metrology, but Wikipedia's coverage of that area seems lacking. Lambiam's answer makes sense if the circles really are circles, but if they're lacking in concentricity they may well also be lacking in circularity. Maybe a Google search will find something more relevant? —David Eppstein 17:28, 27 February 2007 (UTC)

:) Thanks you're both awesome. I am thinking metrologically for engineering purposes. I had considered 100(d/(R-r)) as a percentage figure, with 0% being dead on and 50% non-consentric having the smaller center midway down the larger radius. d/(R-r) will certainly work, but I'd like to know if that is a common convention among those who deal with these things on a regular basis. Is there an engineering/metrology/drafting discriptor commonly employed as a convention? - Many Thanks (4crates 03:16, 2 March 2007 (UTC))

Squaring the circle

I understand that this is impossible with just a pair of compasses and a straight-edge, but is it possible with compasses and a ruler? How would the ruler have to be marked? Do we need the sqrt(pi) marked on the ruler, or would any two points suffice? Is it possible to produce a ruler that has a tick at exactly sqrt(pi) from the zero-tick? Vonity 23:24, 27 February 2007 (UTC)

A "straight edge" is a ruler. Or is it the other way around? Either way you cannot square a circle using only rational numbers. So what if you have the sqrt(pi) marked on your ruler? You cannot multiply two numbers on a ruler.

Pi*r*r = B*B

So B = sqrt(pi) * r

So how do you plan to "multiple" sqrt(pi) with r using your ruler? 202.168.50.40 00:52, 28 February 2007 (UTC)

A straight edge does not have any marks. The idealized straight edge in the straight-edge-and-compass construction problems allows you to construct the line between two given (i.e.: previously constructed) points, not measure distances or construct segments of a certain distance. Phils 01:15, 28 February 2007 (UTC)

Unlike trisecting the angle and doubling the cube, squaring the circle can't be done with compass and marked straightedge. I'm fairly sure that since the operations are non-linear, a pre-marked ruler won't work either: you'd need a different ruler for each circle you're working on. --Carnildo 01:51, 28 February 2007 (UTC)

A better question seems to be what exactly are the set of algebraic operations that can be constructed with a straight edge and a compass, and then in addition we had a ruler that had 2 markings: 1 marking for 1 sample unit and then 1 marking for 1 pi unit ($\pi$ as a ratio) For that matter the marking could be $e^{3\pi }+sin(4)/\pi$ units for that matter. I quote the current Compass and straightedge constructions

"The only way to construct points is as the intersection of two lines, of a line and a circle, or of two circles. Using the equations for lines and circles, one can show that the points at which they intersect lie in a quadratic extension of the smallest field F containing two points on the line, the center of the circle, and the radius of the circle. That is, they are of the form x + y√k, where x, y, and k are in F."

By adding the ratio $\pi :1$, we've now added $\pi$ to the field F, and thus ${\sqrt {\pi }}$ should now be constructible, unless I'm mistaken. Take this with a grain of salt. Root⁴(one) 07:43, 28 February 2007 (UTC)

Off the top of my head here. Ok, consider this argument. Using chords, you can construct the square root, right? if two chords intersect, then the product of the distances from the intersection point to the edge of the circle on one chord equals the product of the distances from the intersection point to the edge of the circle on the other chord.

Let line segment CB have 1+ pi unit length, and mark where the unit distance 1 occurs at point P. (We can do that by our assumptions here about having a marked ruler). We use the compass to bisect the 1+pi unit length and draw a circle O around it, leaving us with a 1+pi diameter circle. Now, using a compass and straight edge only we can construct a line perpendicular to line segment CB at the point P and see where it passes through O, and call those points A and A'. By some laws of Euclidean Geometry I forget, we can prove AP = A'P. By the law of chords I mentioned len(AP)*len(A'P) = 1*pi. Therefore len(AP) = ${\sqrt {\pi }}$

Am I off my rocker or is this correct? looks like the Power of a point article agrees with me as to what the chord law states, so maybe I'm not. Root⁴(one) 08:10, 28 February 2007 (UTC)

You're fine (at least with the conclusion; I'm too lazy to go over the argument, but it looks like the one we had lectured). You can square the circle with compasses and ruler with distances of 1 and pi marked. What you can't do (but can for angle-trisection and cube-doubling) is do it with compasses and a ruler that is unmarked but you're allowed to make marks on.

In answer to the original problem, it's easy to construct a ruler with a tick at sqrt(pi) from zero: just make any tick, and declare that distance to be sqrt(pi). The hard part is to construct marks at sqrt(pi) and at 1. Whether this can be done depends (I suppose) on exactly which tools you're allowing yourself to do it with. Algebraist 10:39, 28 February 2007 (UTC)