Tuesday, October 29, 2019

The difference between proof and understanding

The mathematical proofs laid out in my previous post (which I am sure very few of you have bothered to read) left me both satisfied and disappointed. Having had only the patchiest of mathematical educations (basic algebra and statistics, plus such rudiments of set theory and symbolic logic as linguists require; no trigonometry or calculus), I took a certain satisfaction in having been able to do it at all -- but it was disappointing to realize that I didn't seem much closer to understanding the patterns than I had been before. Why are they always palindromic, for instance? Saying that their palindromicity can be expressed algebraically as n(n + 1) ÷ 2 ≡ (2k - (n + 1))(2k - n) ÷ 2 (mod k), and that that equation turns out to be true for all natural number values of n and k, just doesn't count as an answer to that question. I can follow each step of the algebra, but in the end I do not feel enlightened; I do not think, "Oh, now I get it!" It is possible to prove something without really understanding it.

Then I read Kevin McCall's much better proofs of the same postulates. What a difference! Where I had hammered out my proofs by algebraic brute force, McCall had understood. -- and left me thinking, in T. H. Huxley's much-quoted words, "How extremely stupid not to have thought of that!"


The heart of McCall's proof is the observation that, in modular arithmetic with modulus k, adding k - n is equivalent to subtracting n. You can easily see this in the most familiar everyday use of modular arithmetic, which is our 12-hour clock, with modulus 12. If you want to get from 11:00 to 7:00, for example, you can either subtract 4 hours or add 12 - 4 = 8 hours.

The series of triangular numbers is generated by starting with 0, then adding 1, then adding 2, then 3, and so on through the succession of natural numbers. Due to the fact that k - -n (mod k), one you've added numbers up to a certain point, you start doing the modular equivalent of subtracting those same numbers in reverse order, creating a palindrome. For example, if the modulus is 7:
  • 0
  • +1
  • +2
  • +3
  • +4 ≡ -3 (mod 7)
  • +5 ≡ -2 (mod 7)
  • +6 ≡ -1 (mod 7) 
  • etc.
Obviously, this will create a repeating palindromic pattern with a period of 7.

Why is the period twice as long for even moduli? Consider the case when the modulus is 6.

  • 0
  • +1
  • +2
  • +3
  • +4 ≡ -2 (mod 6)
  • +5 ≡ -1 (mod 6)
  • +6 ≡ 0 (mod 6)
  • +7 ≡ +1 (mod 6)
  • +8 ≡ +2 (mod 6)
  • +9 ≡ -3 (mod 6)
  • +10 ≡ -2 (mod 6)
  • +11 ≡ -1 (mod 6)
  • etc.
Because the modulus k is even, ÷ 2 ≡ -÷ 2 (mod k). In this case 3 ≡ -3 (mod 6). That means that, when we go through the first cycle of 6 integers, we add 1, add 2, add/subtract 3, subtract 2, and subtract 1. We can think of this as adding or subtracting 3, but whichever it is, we only perform the operation once in a single cycle, so at the end of the cycle we still have something congruent to 3 (mod 6); we have not yet returned to the 0 with which we began. However, if we go through two cycles, we can think of ourselves as adding 3 the first time around and then subtracting it the second time, bringing us back to our starting point. Thus, the period is twice as long for even moduli, and the palindrome is centered on ÷ 2, a number which is special because it alone is congruent to its own negation.


Now I understand -- and just about anyone else can understand, too, without any need to pore over complicated algebraic operations. Congratulations, Kevin McCall; you've really solved this, whereas I was just crunching numbers.

No comments:

Annunciation rescheduled to coincide with eclipse

I just saw this on Ann Barnhardt's blog : March 25th is the fixed date of the great Feast of the Annunciation… BUT since March 25th fall...