[seqfan] Re: Using floretions for primality proofs
Creighton Kenneth Dement
creighton.k.dement at mail.uni-oldenburg.de
Sat Dec 5 00:45:23 CET 2009
Here's my (amature) proof of the conjecture mentioned in my last post.
Again, see
http://mrob.com/pub/math/seq-floretion.html
for an introduction.
CONJECTURE:
If tes(X) = q and tesseq(X) = (tes(X), tes(X^2), tes(X^3), ...) is a
sequence of integers, then
p divides tes(X^p) - q^p for all primes p > 2.
The proof given is based on the bracelet proof of Fermat's Little Theorem:
http://en.wikipedia.org/wiki/Proofs_of_Fermat%27s_little_theorem
The following lemma is almost trivial to mention, but plays a crucial role
in the proof.
LEMMA:
Let G be any group and choose g_1, g_2, ... g_m in G.
Then from
(g_1)*(g_2)*...*(g_m) = u where u is the identity element, it follows that
(g_2)*...*(g_m)*(g_1) = u
Proof (g_2)*...*(g_m) is the unique inverse of g_1 and therefore commutes
with g_1 by the definition of a group. q.e.d. (LEMMA)
Proof of CONJECTURE:
Let p be a prime > 2 and
X = P'ee' + A'i + B'j + C'k + Di' + G'ii' + L'ji' + N'ki' + Ej' + J'ij' +
H'jj' + O'kj' + Fk' + K'ik' + M'jk' + I'kk'
where 'ee' is the identity element (don't worry, we won't actually be
doing complex calculations in this proof with all the letters).
How many terms belong to tes(X^p), i.e. the identity 'ee' from the
expanded product
X^p = (P'ee' + I'kk')*...*(P'ee' + I'kk') ?
Apparently, the answer is 16^{p-1} since we have 16 choices from each set
of parenthesis... except the last set (why?). Now, many of those terms
will cancel out and determining which terms have which signs could get
extremely complicated (the LEMMA will be used to get around the problem).
Disregarding signs, any such term may be seen as a string with p letters.
Assume, for example, that -ADDB...ACMP is one of the actual terms from
tes(X^p). It follows from the distributive law that rotating this string
as a bracelet to form PADDB...ACM must also be a term in the product. The
sign of this term is now critical to the proof since it could either
double or cancel out the term before rotation. However, since the base
vectors 'i, 'j, ... 'ee' can be seen as elements of a group (the factor
space QxQ/{(1,1),(-1,-1)}, where Q is the quaternion group) the above
LEMMA applies, and we conclude the sign of this term must likewise be
negative.
So in our running example, we know there must be terms:
ADDB...ACMP
PADDB...ACM
MPADDB...AC,
etc.
in the expansion of tes(X^p) which all have the same (negative) sign.
Since p is prime > 2, the number of such terms must be p (see above proof
of Fermat's Little Theorem and, if you wish, consider why it doesn't work
for p = 2). Thus, the terms in the expansion of tes(X^p) are partioned
into groups and the number of terms in each group is p - with the
exception of the single term tes(X)^p, which is subtracted off. q.e.d.
Note: For primes p = 3 we have
tes(X^3):
+3.0PHH +6.0LBD -3.0PFF +3.0PMM +6.0DCN -3.0CCP -6.0GOM +3.0NNP +6.0BMF
-3.0PAA -3.0DPD +6.0OEC +6.0KAF +6.0NMJ +6.0HEB -3.0BBP +6.0LKO -6.0NKH
+6.0JAE -6.0LJI +6.0IGH +3.0PJJ +3.0POO +1.0PPP +3.0PII +6.0AGD +6.0FCI
+3.0PGG +3.0PLL -3.0EEP +3.0KKP
Sincerely,
Creighton
To see how this plays out on a concrete example, suppose we wish to
> show:
>
> For prime p, A001333(p) congruent to 1 mod p
>
> Define X = 'ii' + 'ik' + 'ee'
>
> Then tes(X) = 1 and we see that
>
> tesseq(X): [1, 3, 7, 17, 41, 99, 239, 577, 1393, 3363, 8119, 19601,]
> resembles A0001333, apart from the initial term.
>
> Theorem. tesseq(X) is always a 4th order linear recurrence or less for any
> X.
>
> From this it follows that tesseq(X) does, in fact, return A0001333. Thus,
> the requirements of the conjecture are met and we conclude that, if the
> conjecture is correct, p divides tes(X^p) - 1^p = tes(X^p) - 1 =
> A0001333(p) - 1 for all primes.
>
> Note also that (1, tes(X+ee), tes((X+'ee')^2), ...) is the binomial
> transform of (1, tes(X), tes(X^2), ...) and that if tes(X) = 0, then of
> course tes(X+'ee') = 1.
>
> Let's now pick a floretion "at random" and see how the conjecture works in
> this case.
>
> Choose X = 2'i + 5i' - k' + 'ii' + 'kk' + 'ik' + 3'jk' - 2'kj' + 3'ee'
>
> We have tesseq(X) = (3, -5, -15, 1505, 17683, 82411, 121201, 1724769,
> 44697027, 451106875, 2430789969, ...)
>
> which has the generating function (-3 + 41*z - 291*z^2 - 111*z^3)/(-1 +
> 12*z - 82*z^2 + 388*z^3 + 111*z^4)
>
> tes(X) = 3. Therefore
> 3 must divide tes(X^3) - 3^3 = -15 + 27 = 12
> 5 must divide tes(X^5) - 3^5 = 17683 = 17440
> 7 must divide tes(X^7) - 3^7 = 119014 = 2*7*8501
> 11 must divide tes(X^11) - 3^11 = 2430612822 = 2*3*11*36827467
> ...
>
> I'm looking forward to proving the conjecture in its entirety.
>
> Sincerely,
> Creighton
>
>
>
>
>
More information about the SeqFan
mailing list