## How much is enough?

by

If you notice a pattern, how many times do you have to check that it works before being certain. Six? Twenty? Two thousand?

Two favorite examples of mine that demonstrate that patterns can continue for a long time before going awry:

The first example is the polynomial f(n)=n2+41n+41. If you plug in any whole number for n from 1 to 40, then f(n) is a prime number: f(1)=83, f(2)=127, all the way to f(40)=3281. But f(41)=3403=41·83 is not prime. So something that works 40 times in a row might fail.

The second example are the cyclotomic polynomials. Look at polynomials of the form xn-1 that have been factored:

x-1=(x-1)
x2-1=(x-1)(x+1)
x3-1=(x-1)(x2+x+1)
x4-1=(x-1)(x+1)(x2+1)
x5-1=(x-1)(x4+x3+x2+x+1)
x6-1=(x-1)(x+1)(x2+x+1)(x2-x+1)

The last polynomial in each case is the cyclotomic polynomial of order n. [It has a much more technical definition using imaginary numbers and the product of primitive roots of unity]. And at first glance it looks like the coefficients are 0, 1, or -1. Even at second glance or sixth glance, since it’s true for the first 104 cyclotomic polynomials. But not the 105th.

x105-1=(x-1)•(x2+x+1)•(x4+x3+x2+x+1)•
(x6+x5+x4+x3+x2+x+1)•(x8-x7+x5-x4+x3-x+1)•
(x12-x11+x9-x8+x6-x4+x3-x+1)•
(x24-x23+x19-x18+x17-x16+x14-x13+x12-x11
+x10-x8+x7-x6+x5-x+1)•
(x48+x47+x46-x43-x422x41-x40-x39+x36+x35
+x34+x33+x32+x31-x28-x26-x24-x22-x20+x17+x16
+x15+x14+x13+x12-x9-x82x7-x6-x5+x2+x+1)

See those two coefficients of 2 in that last polynomial? So the pattern of coefficients being only 0, 1, or -1 fails. Interestingly, the reason for this initial failure occurring so late in the game is that 105 is the smallest number that has three distinct odd prime factors (105=3·5·7). The integer 385 is also a product of three distinct odd primes (385=3·5·11) and the 385th cyclotomic polynomial is the first one to have a 3 as a coefficient (see Wolfram Mathworld).

Patterns. You just can’t trust them.