Schematic algebra - Self classes

You're reading an English translation of the original Czech page.

Triangle of self classes

Triangle of self classes is a core of the Pascal’s triangle.

                       0
                     1   1
                    0  1  0
                  0  1   1  0
                 0  1  1  1  0
               0  1  2  2  1   0
             0  1  2   3  2  1  0
           0  1   3  5   5  3  1  0
         0  1   3  7   8  7   3  1  0
       0  1   4   9 14  14  9  4   1  0
     0  1   4  12 20  25 20  12  4  1  0
   0  1  5  15  30  42  42 30 15  5  1  0
 0  1  5  18  40  66  75 66  40 18  5  1 0 
0  1  6 22  55  99 132 132 99  55 22 6  1  0

Pascal’s triangle can be derived by summing up of members of triangle of self classes (summation goes through divisors of the order k).

Structure of the triangle relates to Wilson’s prime-number theorem.

Central sequences

Backbone of the self classes triangle is made of two sequences:

Sequence {1,1,2,5,14,42,132,429,1430,...}, i.e. sequence of highest numbers in odd rows 

Sequence {1,1,3,8,25,75,...}, i.e. sequence of highest numbers in even rows 

We will deal mainly with the firsts of them.

Catalan‘s sequence

Catalan‘s triangle

Sequence of numbers {1,1,2,5,14,42,132,429,1430,...} i.e. f_binom_2s1_s /(2s+1) came from so called Catalan triangle:

Catalan, Eugéne Charles
Catalan, Eugéne Charles , 1814-1894
  1 
  1   2 
  1   3   5 
  1   4   9  14
  1   5  14  28  42
  1   6  20  48  90  132

E.Catalan and Rodrigues (1838) used this sequence while solving problem of partitioning of convex n−gon to triangles with help of not-crossing diagonals.

Number of diagonals in n-gon is maximally (n−3) and diagonals separate n-gon into (n−2) triangles.

Number of possible partitions p(n):

          2∙6∙10...∙2(2n−5)        1∙3∙5... ∙(2n−5)
   p(n) = ───────────────── = 2n−2 ────────────────
            (n−1)!                     (n−1)!

  p(n) = f_binom_2n3_n2  / (2n−3)

For s= n−2 (i.e. for s+2 gon) relation gets simpler form [Vilenkin]:

   p(s) = f_binom_2s1_s /(2s+1)

This problem is equivalent to task of putting brackets into expression a+b+c+....
E.g. there exist 5 possible variants of not-crossing diagonals in pentagon and the same number of possible bracketing of expression a+b+c+d.

Recurrent notation

Recurrent notation of Catalan sequence follows from the following schema [Vrba]:

  p3 = 1
  p4 = p3 +p3 = 2
  p5 = p4 +p3p3 +p4 = 5
  p6 = p5 +p3p4 +p4p3 +p5 = 14
  p7 = p6 +p3p5 +p4p4 +p5p3 +p6 = 42
  p8 = p7 +p3p6 +p4p5 +p5p4 +p6p3 +p7 = 132
Modified Pascal triangle
 1 
 1  2 
 1  4   5 
 1  6  14  14 
 1  8  27  48  42 
 1 10  44 110 165 132

Catalan sequence appears also in the following modification of Pascal’s triangle. Let us consider arrangement of numbers given by recurrent relation:

c(n+1,k)= c(n,k−1)+2∙c(n,k)+c(n,k+1):

E.g. 27= 1+2∙6+14, 48 = 6+2∙14+14,...

Spin states

   0 [    0] 0
   1 [    2] 1
   2 [    1] 0 1
   3 [    2] 0 1
   4 [    3] 0 1 1
   5 [    6] 0 1 2
   6 [    9] 0 1 2  3
   7 [   18] 0 1 3  5
   8 [   30] 0 1 3  7   8
   9 [   56] 0 1 4  9  14
  10 [   99] 0 1 4 12  20  25
  11 [  186] 0 1 5 15  30  42
  12 [  335] 0 1 5 18  40  66  75
  13 [  630] 0 1 6 22  55  99 132

Sequence {1,1,2,5,14,42,132,429,1430,...}, i.e. sequence of highest numbers in odd rows, is [2n+1 | n]/(2n+1).

Catalan sequence appears also in triangle constructed in the following way:
  1
  1  5
  1  4 14
  1  3  9  28
  1  2  5  14  42            

.Numbers 1 in the first column.

. Members of the first row are sums of numbers from the left.
E.g. 2 = 1 + 1; 5 = 2 + 3; 14 = 5 + 9; 42 = 14 + 28.

. Members on the nexts rows are sums of numbers from below and from the left upper diagonal.
E.g. 3 = 2 + 1; 9 = 5 + 4; 28 = 14 + 14.

This schema came from [Fišer], particular numbers express numbers of independent spin states (multiplets).

Inversion of Catalan sequence

Let us mark A(x) power progression corresponding to sequence {1,1,2,5,14,42,132,429,1430,...}.

What is the sequence 1/A(x)?  Result  is {1,−1,−1,−2,−5,−14,−42,−132,... } i.e. 1− x∙A(x).

From relation 1/A(x) = 1− x∙A(x) follows:

 x∙A²(x)−A(x) +1 = 0 

Congruence

Wilson‘s levels

We have observed rows of triangles according to given module r in the paragraph Congruence of triangles.

Now let us consider congruence according to prime module p dependent on order of system k (i.e. number of row) by relation p = κ(k).

Let us observe rows of triangles of self classes of systems G(2,k), for k=2p−1, according to module p.

When p is prime then for numbers c= f_binom_2p-1_s , s=1,2..p−1, it holds:

  c  = ±1 (mod p); c/(2p−1) = ±1 (mod p) 

E.g.:

f_binom_3_0 mod 2=+1 f_binom_3_1 mod 2=−1  

f_binom_5_0 mod 3=+1 f_binom_5_1 mod 3=−1 f_binom_5_2 mod 3=+1 

f_binom_9_0 mod 5=+1 f_binom_9_1 mod 5=−1 f_binom_9_3 mod 5=+1 f_binom_9_4 mod 5=−1 . . .

In case k=2p−1 number c denote number of self instances.
Therefore c/(2p−1) is number of self classes.

Triangle of self classes for k =2p−1:

    (p=2)    3:  0   1
    (p=3)    5:    0   1   2
    (p=5)    9:  0   1   4   9  14
    (p=7)   13:    0  1  6  22  55  99 132

These numbers mod p always give +1 or −1:

    (p=2)    3:  0  +1
    (p=3)    5:      0  +1  −1
    (p=5)    9:  0  +1  −1  −1  −1
    (p=7)   13:    0 +1 −1  +1  −1  +1  −1

E.g. for p=7 we have, i.e. 2p−1=13:

    i:          0     1    2      3     4      5     6
    ──────────────────────────────────────────────────────
    c(i):      0    13    78    286   715   1287  1716 ...
    c(i)/13:   0     1     6     22    55     99   132 ...
    mod 7:     0    +1    −1     +1    −1     +1    −1 ...

Congruence according p²

Gauss has shown, that Fermat’s equation xp+yp=zp (for p>>2) can have solution only if p² | Vp(x,y), where Vp(x,y) = (x+y)p − xp − yp (see Cauchy’s polynomials below), i.e. if it holds:

(x+y)p − xp − yp ≡ 0 (mod p²)

If it is not trivial case (p|x or p|y) and congruence does not have solution, then 1.case of LF theorem holds.

Sequences on diagonals

              1
            1   1
          1   2   1
        1   3   3   1
      1   4   6   4   1
    1   5  10  10   5   1 
  1   6  15  20  15   6   1
1   7  21  35  35  21   7   1 

Pascal‘s triangle

Any row in Pascal’s triangle is sum of numbers from the previous row.

So sequence on certain diagonal is sum (resp. differential) sequence of adjacent diagonal.

Let us mark the diagonals by numbers k=0,1,2,3,4... and their sequences by notation {uk(n)}.

   1, 4, 10, 20, 35,...
     3, 6, 10, 15,..
       3, 4, 5,...
         1, 1,.... 

E.g. for k= 3 is u3(n)= {1,4,10,20,35,...}.

Characteristic of this sequence is [1,3,3,1]:

Particular diagonals contain arithmetic sequences. Their characteristics are rows of Pascal’s triangle. Sequence on k-th diagonal is made from numbers f_binom_t_k  and has characteristic determined by numbers f_binom_k_l , where tεN is ordinal number of elements on diagonal and L is level (L=0..k).

Self classes

Diagonals in the triangle of self classes do not make sum or differential sequences. Let us mark {vk,n} sequences on diagonals of triangle of self classes.

Let us find recurrent form of the first progressions of numbers (for n>0)  and look for generating functions:

 k=1: 0,1,1, 1, 1, 1, 1, 1, 1, 1,...        v1,n = v1,n−k     v1(x) = 1/(1−x)
 k=2: 0,1,1, 2, 2, 3, 3, 4, 4, 5,...        v2,n = v2,n−k+1   v2(x) = 1/(1−x²)(1−x)
 k=3: 0,1,2, 3, 5, 7, 9,12, 15, 18,...      v3,n = v3,n−k+k   v3(x) = 1/(1−x³)(1−x)²
 k=4: 0,1,2, 5, 8,14,20,30, 40, 55,...
 k=5: 0,1,3, 7,14,25,42,66, 99,143,...


Relation for higher numbers n gets more complicated. Similar symmetry of characteristics as in Pascal’s triangle exists for diagonals with prime k=p, p>2.
In case p=7, are numbers {0,1,4,12,30,66,132} on both sides of  figures made from differences of these numbers:

   p= 3 :  0,1,0       n= 7 : 0 ,1, 2, 3, 2, 1, 0
            1,1                1, 3, 5, 5, 3, 1
             2                   4, 8,10, 8, 4
                                   12,18,18,12
                                     30,36,30
   p= 5 :   0,1,1,1,0                 66,66 
             1,2,2,1                   132
              3,4,3      
               7,7
               14

(Do have this property of symmetry all sequences with symmetric characteristic?)

Symmetry of characteristics

Let us mark {sp,n} sequences derived from characteristics, that are get from rows of  triangles of self classes in systems G(2,k), where k=p−1 and pε P, P>2:

    k  p Characteristic         Sequence {sp,n}
   ──────────────────────────────────────────────────────────
    2  3 [0,1,0]                {0,1,2, 3, 4, 5, 6, 7, 8, 9, 10}
    4  5 [0,1,1,1,0]            {0,1,3, 7,14,25, 41, 63, 92,129, 175}
    6  7 [0,1,2,3,2,1,0]        {0,1,4,12,30,66,132,245,428,711,1132}
   10 11 [0,1,4,12,20,25,..]    {0,1,...}

Let us compare sequences {sp,n} and sequences {vp,n}.
E.g. for p=5 we get differences {v5,n}−{s5,n}:

 n : 0,1,2,3, 4, 5, 6, 7, 8, 9, 10,...
 v5: 0,1,3,7,14,25,42,66,99,143,...
 s5: 0,1,3,7,14,25,41,63,92,129,175, ...
 ───────────────────────────────────────────────
     0,0,0,0, 0, 0, 1, 3, 7, 14, ...

i.e. in form of polynomials:

 v5(x) = 0+x+3x²+7x³+14x4+25x5+42x6+66x7+ 99x8+...
 s5(x) = 0+x+3x²+7x³+14x4+25x5+41x6+63x7+ 92x8+...
 ─────────────────────────────────────────────────
   1x6+ 3x7+ 7x8+...

We se, that: v5(x) = s5(x) + x5∙s5(x) + (?)

If there is a similar shift also after the next 5 members, it holds:

  vp(x) = sp(x) + xp∙sp(x) +x²p∙sp(x)+ +x³p∙sp(x) + ...

  vp(x) = sp(x) (1+ xp +x²p +x³p+ ...)

In the bracket is sum of geometrical progression, therefore:

 vp(x) = sp(x) / (1− xp

Let us check this relation for p=3 (where more cycles can be seen):

  Function    Sequence
  ───────────────────────────────────────────────
  s3(x)       0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,...
  x3∙s3(x)    0, 1, 2, 3, 4, 5, 6, 7,...
  x6∙s3(x)    0, 1, 2, 3, 4,...
  x9∙s3(x)    0, 1,...
  ───────────────────────────────────────────────
  v3(x)   0, 1, 2, 3, 5, 7, 9, 12, 15, 18, 22,...

Sequences s3(x) has its generating function 1/(1−x)².  So relation v3(x) = s3(x)/(1− x³)  match with mentioned generating function v3(x) = 1/(1− x³)(1−x)².

Equations from rows of triangles

Reciprocal equations get from row of Pascal’s triangle, e.g.. x²+2x+1 = 0 have always solution x=−1. And equations (x+1)k=0 have always k-multiple solution.

Later we will look for regularities in equations from other triangles.

Polynomials of self classes

Assembling of polynomials

Let us make polynomials from numbers in triangle of self classes:

 k polynomials of self classes

 2: 1
 3: x + 1
 4: x²+ 1x +   1
 5: x³+ 2x²+  2x +   1
 6: x4+ 2x³+  3x²+  2x +   1
 7: x5+ 3x4+  5x³+  5x²+  3x +   1
 8: x6+ 3x5+  7x4+  8x³+  7x²+  3x +   1
 9: x7+ 4x6+  9x5+ 14x4+ 14x³+  9x²+  4x + 1
10: x8+ 4x7+ 12x6+ 20x5+ 25x4+ 20x³+ 12x²+4x + 1
11: x9+ 5x8+ 15x7+ 30x6+ 42x5+ 42x4+ 30x³+ 15x²+5x + 1
Partition of polynomials

Polynomials as products of prime factors:

k Partition of polynomial Vk(x)    For x=1 Degree
2 1 1=1 0=0
3 (x+1) 2=2 1=1
4 (x²+x+1) 3=3 2=2
5 (x+1)(x²+x+1) 2∙3=6 1+2=3
6 (x²+x+1)² 3²=9 2∙2=4
7 (x+1)(x²+x+1)² 2∙3²=18 1+2∙2=5
8 (x²+x+1)(x4+2x³+4x²+2x+1) 3∙10=30 2+4=6
9 (x+1)³ (x4+x³+3x²+x+1) 2³∙7 =56 3∙1+4=7
10 (x²+x+1)² (x4+2x³+5x²+2x+1) 3²∙11=99 2∙2+4=8
11 (x+1)(x²+x+1) (x6+3x5+7x4+9x³+7x²+3x+1) 2∙3 ... ∙31=186 1+2 ... +6=9
13 (x+1)(x²+x+1)² (x6+3x5+8x4+11x³+8x²+3x+1) 2∙3² ∙35=630 1+4 ... +6=11
17 (x+1)(x²+x+1)(x12+6x11+26x10+ +75x9+156x8+240x7+277x6…+1) 2∙3 ... ∙1285=7710 1+2 ...+12=15

Note that:

Value of polynomials from substitution x=1 determine number of classes m(2,k) in system G(2,k).

Values for x=1, kεP make Fermat’s coefficients (2k−2)/k.  Divisibility o these values determine also divisibility of polynomials. E.g. for k=11 is 186=2∙3∙31 and therefore corresponding  polynomial is divisible by expression  (x+1)  (x²+x+1), according to values 2 and 3.

For odd k polynomials are divisible by (x+1).  For k= 4,6,7,8,10,11,... polynomials are divisible by (x²+x+1).

Lamé, Gabriel
Lamé, Gabriel [], 1795-1871

Transcription of Fermat‘s theorem

General Lame’s prove of the LF theorem is incorrect, but it uses interesting construction. Lame rewrote expression

xp+yp = zp (for pεP, p>2)

into form:

   (x+y)(x+ry)(x+r²y).....(x+rp−1) = zp,

where r is complex p-th root of numbers 1.

Let use multiple expressions (x+y)(x+ry)(x+r²y)... from the left and remove terms xp+yp (i.e. zp) we get (from assumption rp = 1) the following expressions:

    p  Expression
    ─────────────────────────────────────────────
    3  (x²y+xy²) (1/r+1+r) = 0
    5  (x4y+2x³y²+2x²y³+xy4) (1/r²+1/r+1+r+r²) = 0
    7  (x6y+3x5y2+5x4y3+5x³y4+3x²y5+xy6) (1/r³+1/r²+1/r+1+r+r²+r³) = 0

Coefficients of expressions seem to make rows of triangle of self classes:

    p  Coefficients
    ─────────────────────
    3  1  1 
    5  1  2  2  1
    7  1  3  5  5  3  1
Cauchy, Augustin Louis
Cauchy, Augustin Louis , [koši] 1789-1857

Cauchy‘s polynomials

In connection to Lame’s prove of the Last Fermat theorem (for k=7), Cauchy and Liouville studied (in years 1839-1841) polynomials of the form (x+y)k−(xk+yk).

  R3(x,y) = (x+y)³−x³−y³ = 3xy(x+y)
  R5(x,y) = (x+y)5−x5−y5 = 5xy(x+y)(x²+xy+y²)
  R7(x,y) = (x+y)7−x7−y7 = 7xy(x+y)(x²+xy+y²)²

For odd k (k>1) are Rk(x,y) multiples of x,y and (x+y). For pεP coefficients Rp(x,y) corresponds to rows of triangle of self instances and are therefore divisible by p. After division by p we get coefficients of polynomials of self classes.

For k≡±1 (mod 6) is Rk(x,y) divisible by expression (x²+xy+y²)t, where t=1 for k ≡ −1 (mod 6) and t=2 for k ≡ +1 (mod 6). If pεP, p≡±1 (mod 6) have Rp (x,y) form:

  Rp(x,y) = (x+y)p−xp−yp = p∙xy(x+y)(x²+xy+y²)t∙Cp(x,y)

These relations were studied also by: Cayley (1878), Catalan (1884), Lucas (1888)...). Expressions Cp(x,1) = Cp (x) are called Cauchy’s polynomials .

Degree of polynomials Cp (x) for p=6s±1 is equal to 6(s−1). Polynomials don’t have real roots (there exists relations from their complex roots).

 C5(x)  = 1
 C7(x)  = 1
 C11(x) = x6+3x5+7x4+ 9x³+7x²+3x+1
 C13(x) = x6+3x5+8x4+11x³+8x²+3x+1

Composing of Cauchy polynomials

In connection to problem of the Last Fermat’s theorem polynomials Cp (x) were rewritten with help of expressions v=xy(x+y) a u=(x²+xy+y²) [Ribenboim]:

    C11(x) = (x²+xy+y²)³ +  [xy(x+y)]² = u³+   v²
    C13(x) = (x²+xy+y²)³ + 2[xy(x+y)]² = u³+ 2∙v²

In other cases Waring’s relations are applied or instead Rk(x,y)  expressions Sk(x,y) are used:

Sk(x,y) = (x+y)k+(−1)k∙(xk+yk) = (x+y)k+(−x)k+(−y)k

These expressions help to compose recurrent relations of observed polynomials.

Composing of polynomials of self classes

For prime k are polynomials Rk(x,1) i Sk(x,1) equivalent polynomials self classes V(x).

Let us write several polynomials with help of x and expressions v=(x+1) and u=(x²+x+1):

k Partition of polynomial Vk(x) Substitution
2 1 1
3 (x+1) v
4 (x²+x+1) u
5 (x+1)(x²+x+1) vu
6 (x²+x+1)²
7 (x+1)(x²+x+1)² vu²
8 (x²+x+1)(x4+2x³+4x²+2x+1) u(v4−2xu)
9 (x+1)³ (x4+x³+3x²+x+1) v³(v4−3xu)
10 (x²+x+1)² (x4+2x³+5x²+2x+1) u²(u²+3x²)
11 (x+1)(x²+x+1) (x6+3x5+7x4+9x³+7x²+3x+1) vu (u³+2x²v²)
13 (x+1)(x²+x+1)² (x6+3x5+8x4+11x³+8x²+3x+1) vu² (u³+3x²v²)
17 (x+1)(x²+x+1)(x12+6x11+26x10+ +75x9+156x8+240x7+277x6…+1) vu (u6+5x²u4+5x³u³+x4v4)

Classes of polynomials

Polynomials Divisors 
──────────────────────────
V3(x), V9(x) v
V4(x), V10(x) u
V5(x), V11(x), V17(x) vu
V6(x) u2 
V7(x), V13(x) vu2
V8(x) u

Divisibility of polynomials Sk(x) depends on their assignment to classes according to module 6.

The same regularity is observed also for polynomials Vk(x).

Differential sequences

Let us observe the numbers from differential sequences on diagonals.

 d= 1:   0,1,1,1,1,1,1,...

 d= 2:   0,1,1,2,2,3,3,...
          1,0,1,0,1,0,1,0,

 d= 3:   0,1,2,3,5,7,9,12,15,18,...
          1,1,1,2,2,2,3,3,3,
           0,0,1,0,0,1,0,0,

 d= 4:   0,1,2,5,8,14,20,30,40,55,70,...
          1,1,3,3, 6, 6,10,10,15,15,
           0,2,0, 3, 0, 4, 0, 5, 0

 d= 5:   0,1,3,7,14 ,25,42,66,99,143,200,273,364,...
          1,2,4,7 ,11,17,24,33, 44, 57, 73, 91,
           1,2,3 , 4, 6,7, 9, 11, 13, 16, 18,
            1,1, 1, 2, 1, 2, 2,  2,  3,  2,
             0, 0, 1,-1, 1, 0, 0, 1,  -1,

 d= 6: 0,1,3,9,20,42,75,132,212,333,497,728,...
        1,2,6,11,22,33,57,80,121,164,231,
         1,4,5,11,11,24,23,41, 43, 67,
          3,1,6, 0, 13,-1,18,2, 24
          -2,5,-6,13,-14,19,-20,22,
            7,-11,19,-27,33,-39,42, ...

 d= 7: 0,1,4,12,30,66,132 , 245,429,715,1144,...
        1,3,8,18,36,66 , 113,184,286,429,
         2,5,10,18,30 , 47,71,102,143,
          3,5,8,12 , 17, 24, 31, 41,
           2,3,4 , 5,  7,  7,  10,
            1 , 1 , 1, 2,  0,  3,
             0 , 0, 1, -2, 3,

When d is prime the sequences seems to be simpler.

Symmetry

There is certain symmetry in differenial sequences, if number n is prime.

E.g.in case n=7, numbers 0,1,4,12,30,66,132 are on both sides of figures:
n= 1 :  0                n= 7 : 0 ,1, 2, 3, 2, 1, 0
                                  1, 3, 5, 5, 3, 1
n= 2 :  0,1                        4, 8,10, 8, 4
         1                          12,18,18,12
                                      30,36,30
n= 3 :  0,1,0                          66,66
         1,1                            132
          2
n= 5 :  0,1,1,1,0
          1,2,2,1
           3,4,3
            7,7
             14

Recurent sequences

Let us again look for sequences ak(n) on diagonals of triangles of self classes.
n=1: 0,1,1, 1, 1, 1, 1, 1, 1, 1,...
n=2: 0,1,1, 2, 2, 3, 3, 4, 4, 5,...
n=3: 0,1,2, 3, 5, 7, 9,12, 15, 18,...
n=4: 0,1,2, 5, 8,14,20,30, 40, 55,...
n=5: 0,1,3, 7,14,25,42,66, 99,143,...

Let sequences {rk(n)} are defined by recurent rules:

Sequences rk(n) have form:

 Fn,c= 1/ (1 - xc) (1 - x)n - 1 

Case c=n.
For n=1,2,3 recurrent {rk(n)} corresponds to sequences of self classes {ak(n)}.

For n=1,2..5 we get sequences: