Supppose there are integers $a_1,a_2,dots$ and a polynomial $p$ so that the integers $p(a_1),p(a_2)...$ satisfy some linear recurrence, i.e. $sum p(a_i)x^i$ is a rational function of $x$. Must integers $b_iin p^{-1}(p(a_i))$ so that $sum b_ix^i$ is a rational function, necessarily exist?
(The answer is no if we ask for the function $sum a_i x^i$ to be rational, as can be seen when $p(t)=t^2$ and $a_i$ being a random sequence of $pm1$)
Matthias' polemics are funny at points but also misleading in several respects:
ZFC also has enormous length and depth of deductions for trivial material. According to Norman Megill's metamath page, "complete proof of 2 + 2 = 4 involves 2,452 subtheorems including the 150 [depth of the proof tree] above. ... These have a total of 25,933 steps — this is how many steps you would have to examine if you wanted to verify the proof by hand in complete detail all the way back to the axioms." Megill's system is based on a formalism for substitutions so there may be an enormous savings here compared to the way in which Matthias performs the counts (i.e., the full expanded size in symbols) for Bourbaki's system. If I correctly recall other information from Megill about the proof length he estimated for various results in ZFC, the number of symbols required can be orders of magnitude larger and this is what should be compared to Matthias' numbers.
The proof sizes are enormously implementation dependent. Bourbaki proof length could be a matter of inessential design decisions. Matthias claims at the end of the article that there is a problem using Hilbert epsilon-notation for incomplete or undecidable systems, but he gives no indication that this or any other problem is insurmountable in the Bourbaki approach.
Indeed, Matthias himself appears to have surmounted the problem in his other papers, by expressing Bourbaki set theory as a subsystem of ZFC. So either he has demonstrated that some reasonably powerful subsystems of ZFC have proofs and definitions that get radically shorter upon adding Replacement, or that the enormous "term" he attributes to the Theorie des Ensembles shrinks to a more ZFC-like size when implemented in a different framework.
EDIT. A search for Norman Megill's calculations of proof lengths in ZFC found the following:
"even trivial proofs require an
astonishing number of steps directly from axioms. Existence of the
empty set can be proved with 11,225,997 steps and transfinite recursion
can be proved with 11,777,866,897,976 steps."
and
"The proofs exist only in principle, of course, but their
lengths were backcomputed from what would result from more traditional
proofs were they fully expanded. ..... In the current version of my proof
database which has been reorganized somewhat, the numbers are:
empty set = 6,175,677 steps
transf. rec. = 24,326,750,185,446 steps"
That's only the number of steps. The number of symbols would be much, much higher.
Yesterday, in the short course on model theory I am currently teaching, I gave the following nice application of downward Lowenheim-Skolem which I found in W. Hodges A Shorter Model Theory:
Thm: Let $G$ be an infinite simple group, and let $kappa$ be an infinite cardinal with $kappa leq |G|$. Then there exists a simple subgroup $H subset G$ with $|H| = kappa$.
(The proof, which is short but rather clever, is reproduced on p. 10 of http://www.math.uga.edu/~pete/modeltheory2010Chapter2.pdf.)
This example led both the students and I (and, course mechanics aside, I am certainly still a student of model theory) to ask some questions:
$1$. The theorem is certainly striking, but to guarantee content we need to see an uncountable simple group without, say, an obvious countable simple subgroup. I don't know that many uncountable simple groups. The most familiar examples are linear algebraic groups like $operatorname{PSL}_n(F)$ for $F$ an uncountable field like $mathbb{R}$ or $mathbb{C}$. But this doesn't help, an infinite field has infinite subfields of all infinite cardinalities -- as one does not need Lowenheim-Skolem to see! (I also mentioned the case of a simple Lie group with trivial center, although how different this is from the previous example I'm not sure.) The one good example I know is supplied by the Schreier-Ulam-Baer theorem: let $X$ be an infinite set. Then the quotient of $operatorname{Sym}(X)$ by the normal subgroup of all permutations moving less than $|X|$ elements is a simple group of cardinality $2^{|X|}$. (Hmm -- at least it is when $X$ is countably infinite. I'm getting a little nervous about the cardinality of the normal subgroup in the general case. Maybe I want an inaccessible cardinal or somesuch, but I'm getting a little out of my depth.) So:
Are there there other nice examples of uncountable simple groups?
$2$. At the beginning of the proof of the theorem, I remarked that straightforward application of Lowenheim-Skolem to produce a subgroup $H$ of cardinality $kappa$ which is elementarily embedded in $G$ is not enough, because it is not clear whether the class of simple groups, or its negation, is elementary. Afterwards I wrote this on a sideboard as a question:
Is the class of simple groups (or the class of nonsimple groups) an elementary class?
Someone asked me what techniques one could apply to try to answer a problem like this. Good question!
$3$. The way I stated Hodges' result above is the way it is in my lecture notes. But when I wrote it on the board, for no particular reason I decided to write $kappa < |G|$ instead of $kappa leq |G|$. I got asked about this, and was ready with my defense: $G$ itself is a simple subgroup of $G$ of cardinality $|G|$. But then we mutually remarked that in the case of $kappa = |G|$ we could ask for a proper simple subgroup $H$ of $G$ of cardinality $|G|$. My response was: well, let's see whether the proof gives us this stronger result. It doesn't. Thus:
Let $G$ be an infinite simple group. Must there exist a proper simple subgroup $H$ of $G$ with $|H| = |G|$?
Wait, I just remembered about the existence of Tarski monsters. So the answer is no. But what if we require $G$ to be uncountable?
Eric Broug in his book Islamic Geometric Patterns gives
straightedge and compass construction of some simpler patterns.
It is clear his techniques will provide constructions for many
Islamic patterns.
Looking at formal constructibility, the Wikipedia pages gives Gauss' result that
7, 9, 11, 13, 14, 18... etc sided polygons are not constructible. Hence the pattern
http://tilingsearch.org/HTML/data160/J43C.html
is not constructible since it contains a regular
9-pointed star polygon.
I have over 800 Islamic patterns on my web site but
I use a computer and trigonometry to produce my images. It seems that
about 40 Islamic patterns on my site are not constructible.
Given an Islamic pattern that is not excluded from construction by Gauss'
result, it is almost certainly constructible if the following is true:
Given two points on the plane, a polygon ($n$ sides) can be constructed with the two points
as an edge, provided $n$ is not equal to 7, 9, 11, 13, 14, 18... etc.
This result would allow patterns to be built up piece-by-piece.
EDIT, Will Jagy: from his profile page, the OP's website, in this address preset to display the tilings in a slideshow format on a web browser, is at
In number theory, here are four applications of techniques or results in first-year calculus.
(1) Finding equations of tangent lines by first-semester calculus methods lets us add points on elliptic curves using the Weierstrass equation for the curve. This is more algebraic geometry than number theory, so I'll add that the methods show if the Weierstrass equation has rational coefficients then the sum of two rational points is again a rational point.
(2) The recursion in Newton's method from differential calculus is the basic idea behind Hensel's lemma in $p$-adic analysis (or, more simply, lifting solutions of congruences from modulus $p$ to modulus $p^k$ for all $k geq 1$).
(3) The infinitude of the primes can be derived from the divergence of the harmonic series (the zeta-function at 1), which is based on a bound involving the definition of the natural logarithm as an integral.
(4) Unique factorization in the Gaussian integers can be derived from the Leibniz formula
$$
frac{pi}{4} = 1 - frac{1}{3} + frac{1}{5} - frac{1}{7} + frac{1}{9} - cdots = sum_{n geq 0} frac{(-1)^n}{2n+1}
$$
by interpreting it as a case of Dirichlet's class number formula $2pi h/(wsqrt{|D|}) = L(1,chi_D)$ for $chi_D$ the primitive quadratic character associated to ${mathbf Q}(sqrt{D})$ where $D$ is a negative fundamental discriminant, $h$ is the class number of ${mathbf Q}(sqrt{D})$ and $w$ is the number of roots of unity in ${mathbf Q}(sqrt{D})$. Taking $D = -4$ turns the left side into $2pi h/(4sqrt{4}) = (pi/4)h$, so the Leibniz formula is equivalent to $h = 1$, which is another way of saying $mathbf Z[i]$ is a PID or equivalently (for Dedekind domains) a UFD.
Here are two more applications, not in number theory directly.
(5) Gerry Edgar mentions in his answer Niven's proof of the irrationality of $pi$, which is available in Spivak's calculus book. The same ideas imply irrationality of $e^a$ for every positive integer $a$, which in turns easily implies irrationality of $e^r$ for nonzero rational $r$ and thus also irrationality of $log r$ for positive rational $r not= 1$. The calculus fact in the proof of irrationality of the numbers $e^a$ is that for all positive integers $n$ the polynomial
$$
frac{x^n(1-x)^n}{n!}
$$
and all of its higher derivatives take integer values at $0$ and $1$. That implies a certain expression involving a definite integral is a positive integer, and then with the fundamental theorem of calculus that same expression turns out to be less than 1 for large $n$ (where "large" depends on the hypothetical denominator of a rational formula for $e^a$), and that is a contradiction.
(6) Prove that if $f$ is a smooth function (= infinitely differentiable) on the real line and $f(0) = 0$ then $f(x) = xg(x)$ where $g$ is a smooth function on the real line. There is no difficulty in defining what $g(x)$ has to be if it exists at all, namely
$$
g(x) = begin{cases}
f(x)/x, & text{ if } x not= 0, \
f'(0), & text{ if } x = 0.
end{cases}
$$
And easily the function defined this way is continuous on the real line and satisfies $f(x) = xg(x)$. But why is this function smooth at $x = 0$ (smoothness away from $x = 0$ is easy)? You can try to do it using progressively messier formulas for higher derivatives of $g$ at 0 by taking limits, but a much slicker technique is to use the fundamental theorem of calculus to write
$$
f(x) = f(x) - f(0) = int_0^x f'(t),dt = xint_0^1 f'(xu),du,
$$
which leads to a different formula for $g(x)$ that doesn't involve cases:
$$
g(x) = int_0^1 f'(xu),du.
$$
If you're willing to accept differentiation under the integral sign (maybe that's not in the first-year calculus curriculum, but we used first-year calculus to get the slick formula for $g(x)$) then the right side is easily checked to be a smooth function of $x$ from $f$ being smooth.
If you want to teach something intriguing, you should do something that introduces a new geometric idea while also involving algebra in an essential way. I recommend that you give an introduction to the projective plane, showing the other students that it is a natural extension of ordinary space which makes some geometric properties more uniform (such as intersection properties of curves), gives a fruitful new way to think about old topics (like asymptotes), and lets you do things that are impossible to conceive without it (reducing rational points mod $p$). There should be substantial interplay between algebra and geometry, but make sure to draw pictures to emphasize the geometric aspects.
In algebra, we can conceive of the quadratic formula in a uniform manner, but the ancient Greeks [Edit: Babylonians, not Greeks] couldn't do this because they didn't have the idea of negative numbers. So they had several quadratic formulas on account of not being able to write something as simple as $ax^2 + bx + c = 0$ at one stroke (for any signs on $a, b$, and $c$, with $a$ nonzero). Our extended skill at algebra lets us work with one case where the ancients had to take multiple cases. We can also say with complex numbers that any quadratic equation has two roots, allowing for a double root to count as one root with multiplicity two.
The thrust of what comes next is to extend the plane so that geometric properties become nicer in a similar way the algebra is becoming nicer when we use more general number systems.
Consider the intersection properties of lines in the plane. There is a dichotomy: usually two lines in the plane meet in one point, but some pairs of lines (the parallel ones) meet in no points. Let's see what this looks like under stereographic projection. Lines in the plane become circles through the north pole, but not including the north pole itself. It's natural to close up the image and take that whole circle as a substitute for the original line. So we can see that lines in the plane naturally close up into circles through the north pole. Under stereographic projection, the old dichotomy between parallel and non-parallel lines takes on a new appearance: a pair of non-parallel lines corresponds under stereographic projection to a pair of circles intersecting in two different points, one of which is the north pole, while a pair of parallel lines corresponds under stereographic projection to a pair of circles which are tangent at the north pole. It is natural to think of two tangent circles as having their point of tangency be an intersection point of multiplicity two, much like a quadratic polynomial can have a double root. So after stereographic projection we can "see" two points of intersection for any pair of lines. This geometric construction is something like the algebraic use of more general number systems to find roots to all quadratic equations. The moral to take from this example is that in a larger space, curves that used to not intersect may now intersect (or rather, their natural closures in the new space intersect) with a uniform count of the number of intersection points. If the students agree that enlarging number systems to create solutions to polynomial equations is good, they should agree that enlarging space to make intersection properties more uniform is good too. Another important feature is that the sphere, like the plane, is a homogeneous object: we can transform (rotate) the space to carry one point to any other point. On the sphere as a space in its own right, there is truly nothing special about the north pole.
An even better geometric extension of the plane is the projective plane, although at first it will feel unfamiliar and strange because you can't see it all at once.
You should introduce it in a uniform manner as points described with homogeneous coordinates $[x,y,z]$ where $x$, $y$, and $z$ are not all 0 and, say,
$$
[3,6,2] = [1,2,2/3] = [1/2,1,1/3] = [3/2,3,1] text{ and } [0,5,0] = [0,1,0].
$$
Although it is impossible to see the whole projective plane at once, we can get glimpses of large parts of it using three different charts: $U_0$ is the points where $x not= 0$, $U_1$ is the points where $y not= 0$ and $U_2$ is the points where $z not= 0$. These three charts together cover the projective plane. Any nonzero coordinate can be scaled to 1 and that fixes the other two homogeneous coordinates of the point, e.g., $[x,y,1] = [x',y',1]$ if and only if $x = x'$ and $y = y'$. This means we can identify each of $U_0$, $U_1$, and $U_2$ with the usual plane (e.g., identify $U_2$ with ${mathbf R}^2$ by identifying $[x,y,1]$ with $(x,y)$). This means the projective plane locally looks like the plane, much like the sphere does, except we can't see all of it at the same time as we can with the sphere.
(In case you want to show students that the projective plane is a really natural model of something they have known in another context, think about nonzero ideals in ${mathbf R}[x]$. Any ideal has a generator, but the polynomial generator is only defined up to a nonzero scaling factor. Usually we normalize the generator to be monic, but if we don't want to insist on a particular choice of generator then the right model for the generator is a point in projective space. In particular, for any nonzero ideal $(f(x))$ where $deg f(x) leq 2$, write $f(x) = ax^2 + bx + c$; the coefficients $a, b, c$ are only defined up to an overall scaling factor, so the point $[a,b,c]$ is one way to think about that ideal.)
Next introduce curves in the projective plane as solutions to homogeneous polynomial equations in $x$, $y$, and $z$ and explain what the algebraic process of homogenization and dehomogenization of polynomials is, e.g., it makes $y = 2x + 1$ into $y = 2x + z$ or $x^2 - y^2 = x+ 1$ into $x^2 - y^2 = xz + z^2$. In particular a line in the projective plane is the solution set to any equation $ax + by + cz = 0$ where the coefficients are not all 0.
Now let's look at what a point on a specific curve in the projective plane looks like in each of the three standard charts, carry out the same kind of calculus computation in each chart, and compare the results with each other. We will use the curve $C : x^2 + y^2 = z^2$ in the projective plane (not to be confused with a surface in 3-space given by the same equation) and the points $P = [3,4,5]$ and $Q = [1,0,1]$ which lie on $C$. How do $C$, $P$, and $Q$ appear in each of the charts $U_0$, $U_1$, and $U_2$?
a) In $U_0$, which is identified with the plane by $[x,y,z] mapsto (y/x,z/x)$, $C$ becomes the hyperbola $z^2 - y^2 = 1$, $P$ becomes $(4/3,5/3)$, and $Q$ becomes $(0,1)$. Here we identify $U_0$ with the usual $yz$-plane. By calculus, the tangent line to $z^2 - y^2 = 1$ at the point $(4/3,5/3)$ is $z = (4/5)y + 3/5$ and the tangent line at $(0,1)$ is $z = 1$.
Note that we actually miss two points from $C$ when we look at the intersection of it with $U_0$: $[0,1,pm 1]$.
b) In $U_1$, $C$ becomes the hyperbola $z^2 - x^2 = 1$ in the $xz$-plane, $P$ becomes the point $(3/4,5/4)$ with tangent line $z = (3/5)x + 4/5$, and $Q$ doesn't actually live in this chart (kind of like the north pole under stereographic projection not going to anything the in the plane). Here two points from $C$ are missing: $[1,0,pm 1]$.
c) In $U_2$, $C$ becomes the circle $x^2 + y^2 = 1$, $P$ becomes $(3/5,4/5)$ with tangent line $y = (-3/4)x + 5/4$, and $Q$ becomes $(1,0)$ with tangent line $x = 1$. Every point from $C$ lies in $U_2$, so no points are missing here. We see the "complete" curve in this chart.
It is essential to draw three pictures here (of the $yz$-plane, $xz$-plane, and $xy$-plane) and mark $P$ and $Q$ in each (except you don't see $Q$ in the $xz$-plane).
Now comes the beautiful comparison step: in all three charts the homogenization of the tangent line at $P$ is exactly the same equation: $3x + 4y = 5z$. The tangent line at $Q$ in $U_0$ and $U_2$ homogenizes in both cases back to $x = z$. This suggests there should be an intrinsic concept of tangent line in the projective plane to the curve $C$ at the points $P$ and $Q$, and you can compute the tangent line by looking at any chart containing the relevant point of interest, doing calculus there, and then homogenizing back. The homogenization of your ordinary linear equation to a homogenuous linear equation will always be the same, and its solutions in the projective plane define the tangent line to the projective curve at that point.
As further evidence of the consistency of this new space and the geometry in it, look at the intersections of the two tangent lines at $P$ and $Q$: in $U_0$ -- the $yz$-plane -- the tangent lines meet in $(1/2,1)$ while in $U_2$ -- the $xy$-plane -- the tangent lines meet in $(1,1/2)$. These points both homogenize back to the same point $[2,1,2]$, which is the unique (!) point in the projective plane satisfying $3x + 4y = 5z$ and $x = z$.
Remember that $Q$ went missing in the chart $U_1$? Well, its tangent line did not go missing: the projective line $x = z$ in the projective plane meets the chart $U_1$ in the ordinary line $x = z$ of the $xz$-plane, which is an asymptote to the piece of $C$ we can see in $U_1$. This is really amazing: asymptotes to (algebraic) curves in the usual plane are "really" the tangent lines to missing points on the complete version of that curve in the projective plane. To see this from another point of view, move around $C$ clockwise in the chart $U_2$ (where it's a circle) and figure out the corresponding motion along the piece of $C$ in the chart $U_0$ (where it's a hyperbola): as you pass through the point $Q = (1,0)$ in $U_2$, what happens in the chart $U_0$ is that you jump off one branch of the hyperbola onto the other branch by skipping through an asymptote, sort of. (There is a second point on $C$ in $U_2$ that you don't see in $U_0$ -- the point $R = [-1,0,1]$ is $(-1,0)$ in $U_2$ -- and paying attention to that point may help here.)
The conic sections -- parabolas, hyperbolas, and ellipses -- which look quite different in ${mathbf R}^2$, simplify in the projective plane because they all look like the same kind of curve (once you close them up): $y = x^2$ becomes $yz = x^2$, $xy = 1$ becomes $xy = z^2$, and $x^2 + y^2 = 1$ becomes $x^2 + y^2 = z^2$, which is the same as $x^2 = (z-y)(x+y) = z'y'$, where $z' = z-y$ and $y' = z+y$. I like to think about this as a fancy analogue of the Greek [Edit: Babylonian] use of many forms of the quadratic formula because they didn't have the right algebraic technique to realize there is one quadratic formula. Using the projective plane we see there is really one conic section.
You might want to show by examples the nicer intersection properties of lines in the projective plane: any two lines in the projective plane meet in exactly one point. This is just a glimpse of the fact that curves in the projective plane have nicer intersection properties than in the ordinary plane, but to get the correct theorem in that direction for curves other than lines, you need to (a) work over the complex numbers and (b) introduce an appropriate concept of intersection multiplicity for intersection points of curves, somewhat like the idea of tangent circles intersecting in a point of multiplicity two which I mentioned earlier. The relevant theorem here is Bezout's theorem, but to state it correctly is complicated precisely because it is technical to give a good definition of what the intersection multiplicity is for two curves meeting at a common point.
For the student who wants to be a number theorist, compare reduction mod $p$ in the usual plane and the projective plane. In the study of Diophantine equations (e.g., to show $y^2 = x^3 - 5$ has no integral solutions), it is very useful to reduce mod $p$, and there is a natural way to reduce a point in ${mathbf Z}^2$ modulo $p$ However, there's no reasonable way to reduce all points in ${mathbf Q}^2$ modulo $p$: when the rational numbers have denominator divisible by $p$, you can't make sense of them mod $p$: we can reduce $(-7/4,51/8)$ mod 5, for example, but not mod 2. In the projective plane, however, we can reduce rational points mod $p$ by the idea of choosing a set of primitive integral coordinates, where the homogeneous coordinates are relatively prime. For example, $[-7/4,51/8,1] = [-14,51,4]$ in ${mathbf P}^2({mathbf Q})$, and this can be reduced mod $p$ for any $p$ at all. For example, in ${mathbf P}^2({mathbf F}_2)$ it becomes $[0,1,0]$.
(There is another primitive set of homogeneous coordinates for the point, namely $[14,-51,-4]$, but that reduces mod $p$ to the same thing as before, so this reduction mod $p$ process is well-defined.) This suggests that the projective plane has better mapping properties than the usual plane, in some sense.
Any pure mathematician will from time to time discuss, or think about, the question of why we care about proofs, or to put the question in a more precise form, why we seem to be so much happier with statements that have proofs than we are with statements that lack proofs but for which the evidence is so overwhelming that it is not reasonable to doubt them.
That is not the question I am asking here, though it is definitely relevant. What I am looking for is good examples where the difference between being pretty well certain that a result is true and actually having a proof turned out to be very important, and why. I am looking for reasons that go beyond replacing 99% certainty with 100% certainty. The reason I'm asking the question is that it occurred to me that I don't have a good stock of examples myself.
The best outcome I can think of for this question, though whether it will actually happen is another matter, is that in a few months' time if somebody suggests that proofs aren't all that important one can refer them to this page for lots of convincing examples that show that they are.
Added after 13 answers: Interestingly, the focus so far has been almost entirely on the "You can't be sure if you don't have a proof" justification of proofs. But what if a physicist were to say, "OK I can't be 100% sure, and, yes, we sometimes get it wrong. But by and large our arguments get the right answer and that's good enough for me." To counter that, we would want to use one of the other reasons, such as the "Having a proof gives more insight into the problem" justification. It would be great to see some good examples of that. (There are one or two below, but it would be good to see more.)
Further addition: It occurs to me that my question as phrased is open to misinterpretation, so I would like to have another go at asking it. I think almost all people here would agree that proofs are important: they provide a level of certainty that we value, they often (but not always) tell us not just that a theorem is true but why it is true, they often lead us towards generalizations and related results that we would not have otherwise discovered, and so on and so forth. Now imagine a situation in which somebody says, "I can't understand why you pure mathematicians are so hung up on rigour. Surely if a statement is obviously true, that's good enough." One way of countering such an argument would be to give justifications such as the ones that I've just briefly sketched. But those are a bit abstract and will not be convincing if you can't back them up with some examples. So I'm looking for some good examples.
What I hadn't spotted was that an example of a statement that was widely believed to be true but turned out to be false is, indirectly, an example of the importance of proof, and so a legitimate answer to the question as I phrased it. But I was, and am, more interested in good examples of cases where a proof of a statement that was widely believed to be true and was true gave us much more than just a certificate of truth. There are a few below. The more the merrier.