The usual n x n bit array_multiplier (MPY) has about n^2 full-adder circuits (FA), which are fed via an n x n array of AND-gates, producing in about 1 nanosecond n^2 bits in the plane, to be added by the FA array to the required 2n bit result. Now the FA array is capable of adding any of the 2^{n.n} bit patterns you could input, but as a multiplier it is only asked to process the 2^{n+n} bit patterns provided via the n x n product gates. Only a fraction 2^(2n) / 2^(n^2) of the possible input patterns that could be processed occurs in practice: the hardware is much too powerful for its purpose.

-- Algebra: . . . Addition (+) and multiplication (.) do have algebraic structure, especially for finite arithmetic (on machines). Then the known residue arithmetic, with some modulus m, say m = 2^k (k bits) is relevant. The structure of the corresponding ring Z (+, .) mod m for integer m>1 is known in some detail, and is considered classic knowledge, since Fermat (1640), Euler (1740) and many others.

Clearly primes play a dominant role, and the structure of Z(.) mod p^k is particularly interesting from a practical point of view for p=2. Usually odd primes p>2 are considered since it is known that the group G_k of units (all n: n^i=1 mod p^k for some i>0) is cyclic, of order:
. . . . . . . |G_k| = (p-1).p^{k-1} for any k>0.
For p=2: G_k is not cyclic, but has a 2-cycle factor C2={-1,1}.

In the detailed structure of Z_k(.) mod p^k, give extra attention to _additive_ properties, since in practice both (+) and (.) occur in comparable amounts (say in DSP). Notice that Fermat's Small Theorem:

It has an interesting additive property, because -1 is in core, and in each even order core-subgroup S, so each even |S| in core has zero sum (pairwise sum 0 mod p^k). It is not difficult to see that more generally:

--- Core thm: . . . Each core subgroup |S| > 1 has zero sum ( mod p^k ).

Also notice the p-th power residues form a subgroup F_k = {n^p} < G_k of order |F_k| = |G_k|/p = (p-1).p^{k-2}, and core A_k < F_k, for k>2 (proper subgroup for at least k=3, beyond Hensel's k>=2 extension lemma: k=2 is nec&suf for FLT root existence mod p^k, but root structure discrimination requires k=3 -- two or three terms in core, see ref[1] ).

The relation to Fermat's . . . FLTcase1 :
. . . . x^p + y^p = z^p (x,y,z>0 coprime to p) has no integer solution, is clear by considering residues mod p^k and a subgroup order |S|=3, occurring iff p=1 mod 6: three p-th power residues with sum 0 mod p^k. First p=7: 18^7 + 1 = 19^7 (mod 7^2). A normal form with one term =1 (or -1) is always possible, since each term has an inverse in G_k.

The Hensel extension lemma, applied here, says: each extension of a p-th power residue n^p mod p^2 is also p-th power residue mod p^k. Precisely because there are |F_k|=|G_k|/p=(p-1)p^{k-2} p-th power residues mod p^k. Hence solutions to FLT mod p^k were considered useless, because of this infinite extension ( Hensel lift ) which would make it "impossible" to derive inequality for integers.

This conclusion is clearly false for solutions with z = x+y in core, as shown in my paper:

It is shown that no other root type can exist, based on considering the symmetries of (+) and (.): complement C(n)=-n, inverse I(n)=1/n as functions (endo-morphisms of Z(+) resp Z(.), in fact order_2 automorphisms) together with the successor function S(n)=n+1.

Their relevance to: a+1= -1/b (etc) is clear, by considering such "loop" of length m to be determined. Iterate composed function -1/(n+1)= SCI(n) which returns 'n' after three iterations: SCI(SCI(SCI(n)))=n, for all n, excluding n=-1 to prevent division by zero. So arithmetic mod p^k allows no looplength beyond 3, which is the number of symmetries +1. <------

For details (incl FLTcase2) see my homepage ref[1].

--- The well known arithmetic problems: - Fermat, Waring, Goldbach -
. . . have in common that they are additive in nature, and the terms
. . . are of "multiplicative type": n^p [F & W] or prime p [G].

The same approach as above: analysis first in residues mod m_k, followed by extension to integers (by the special "EDS" property), is for Goldbach's proof [7] done by induction on k.

Ref[6]: . . " Powersums representing residues mod p^k, from Fermat to Waring "

Published in "Computers and Mathematics, with Applications" V39, N7-8 (mar2000) p253-261

. . The "Waring-for-residues" result is: Z \eqv F+F+F+F (mod p^k), so:
. . Each residue mod p^k is the sum of at most four p-th power residues.
. . (write for brevity: Z= Z_k, G= G_k, F= F_k and A= A_k where useful).

This follows from the residue approach to FLT, by first noticing that apparently set F = {n^p} has anti-closure under (+), and thus is a good additive generating set for the integers (the sum of any two p-th powers is not a p-th power, hence something NEW). -- Core A is also here crucial:

A coset argument shows that all nonzero pairsums of core residues are distinct (upto commutation): |A+A| = |A|.(p-1)/2, where |A|=p-1, yielding all p-th power pairsums F+F= G/2 to cover half of units in G. No attempt has been made (yet) to extend this result to integers, which are known to require a sum of considerably more than four p-th powers (function g(p) increases strongly with p). Except for squares (p=2) where indeed four squares suffice, as already shown by Lagrange (1770) and Euler (1772), compatible with the presented result for residues.

Ref[7]: . . ." Arithmetic with squarefree modulus, its lattice of groups,
. . . . . . . . . . . a prime sieve, and Goldbach's conjecture "

de.arXiv.org abstract . . Goldbach

Goldbach's conjecture:
. . . . . . Each even number >4 is the sum of two odd primes,
follows from additive analysis of the Boolean lattice BL of idempotents in Z_mk(.) Modulus m_k = \prod p_i . . (i = 1..k) is the product of successive primes.

This modulus is chosen to localize the primes between p_k and m_k in the units group G1, and we show that each even idempotent e has successor e+1 in G1. --- Consequently G1 + G1 = E, the set of all even residues in Z_mk. This is a "Goldbach-for-Residues" result (GR) which can be extended to integers by induction on k. The induction base is k=3: GC holds for n < 30 by complete inspection. The induction step extends interval [0,m_k) by +c.m_k for carries c < p_{k+1) to reach all n < m_{k+1}. Failure of GC for any 2j in such interval contradicts GR, establishing GC.

Constructive comments, e.g. on details of the proofs, are welcome. The essence of this approach (semigroup structure analysis, and the EDS property of FLTcase1 solutions in core, to "break through the Hensel lift") was presented at two math conf's:
. . . 1. CVST Prague jul'96, Semigroups and their Applications . . . (digest p7), and
. . . 2. U-Twente . . . apr'98, Netherlands Mathematics Congress . . . (NMC33, ref[5])
. . . . . . and an engineering conf.:
. . . 3. INPG Grenoble dec'96, Logic and Architecture Synthesis . . . (digest p133-140).

Since early 1995, many (>10) trials at publication yielded no relevant critique, other than "this material is not suited for our journal" (see the homepage Campaign item). -- So help in checking the proofs is appreciated.

Re: "-- Fermat's anti-closure n^p(+) as generator" / BOOA constructor ... (sci.math 15may98)

Re: Goldbach's Conjecture novel, contest (& Pertti's plug) ... sci.math 29mar2000

--------------------------------------------------------------------------
Subject:      Re: fermat
Author:       Nico Benschop 
Date:         19 Jan 99 08:29:04 -0500 (EST)  news:sci.math

There _is_ a much simpler and direct way to prove FLT(case1), by
extending Fermat's Small Theorem: n^p = n (mod p) to k>1 digits base p
(prime p>2). In fact case1 (of 2 cases) has xyz <>0 mod p in the FLT
eqn: x^p + y^p = z^p ..[1] (only prime exponents need be considered).

A counter example (positive integers x,y,z solving [1]) should at
least hold mod p^2, for which there are p^2 - p = (p-1)p residues
coprime to p (re: case1). It is known that these form a cycle G (group)
generated by the powers g^i of just one g, written G = g*, and
containing the unity element 1.

So there is a p-1 subcycle, consisting of the p-1 distinct powers
(g^p)^i mod p^2. Notice that they are p-th powers, since (g^p)^i =
(g^i)^p, and let us call this p-1 cycle the "core" of G, and it's
elements (coprime to p) are formally called the "units" of Z_k(.) :
the semigroup of multiplication mod p^k.

In general, all residues mod p^k coprime to p form a group G_k of
order p^k - p^{k-1} = (p-1)p^{k-1|, known to be cyclic (one generator)
for every precision k>0. But we need only k=2 for the FLTcase1 proof!

Because of the lemma:
 Each solution "in core" of [1] mod p^k has (due to n^p=n in core):
            (x+y)^p = x+y = x^p + y^p (mod p^k),
 thus has Exponent p Distributing over a Sum (EDS property).

This implies that such residues can never provide a solution for
the corresponding k-digit integers X,Y,Z, since (X+Y)^p > X^p + Y^p
with terms < p^{kp}.

Moreover, notice that each solution mod p^k (any k>1) also holds
for k=2 (the least significant 2 digits) -- which is a necessary
condition for any integer solution! And every solution for residues
is in core mod p^2. Hence: no integer solution exists, for FLTcase1.

For more detail, e.g. the general form of solutions of [1] mod p^k,
and the corresponding structures in Z(.) mod p^k, & FLTcase2, see:

http://de.arXiv.org/abs/math.GM/0103014      : Abstract + full text.
http://www.iae.nl/users/benschop/nfb0.dvi : Full paper, 12pgs + 2appx
http://www.iae.nl/users/benschop/ferm.htm : Did F find a^3=1 mod 7^2 ?
http://www.iae.nl/users/benschop/campaign.htm       (intro)

And let me know what you think of it. Ciao, Nico Benschop.
----------------------------------------------------------------------

Subject:  Re: Intuition in mathematics
   Date:  Fri, 12 May 2000 09:57:06 GMT
   From:  Nico Benschop
Organization:   Research
  Newsgroups: sci.math
------
Stephen Norris wrote:
>
> Nico Benschop wrote:
> > Then consider the (infinite) group of all permutations of
> > Z = 0{-1,+1}* (the integers, which is a group under addition),
> > yielding the infinite symmetric group Z! -- And all I'm saying is
> > that 2^Z has a cardinality of at most that of Z! -- while Z! has
> > only three sequential generators Z! = {-1,+1, swap2}* , where
> > 'swap2' permutes any two integers, say 0 <-->1, and fixes all
> > others, see also
> > http://piazza.iae.nl/users/benschop/ism.htm (Integer State Machines)
> > So |2^w| <= |Z!| , where Z! is finitely generated (3 generators).
> > Is'nt that interesting?-)
>
> I've just looked again at the above.
> Am I right in suggesting that your methods should be capable
> of giving the best bitwise representation of the prime number
> series (eg for computer storage)?

I would'nt know, never thought about it;-)

BTW: what you call my 'methods' is just another way of looking at
Cantor's diagonal, implying a square w x w table, and consider not
just one diagonal_inverted (binary), but ALL w! row permutations
of one such (arbitrarily chosen) table with corresponding diagonals.
A generative view, mapping all 2^Z subsets 1-1 into fixed-point of
permutations of Z. Showing that a 'linear' model of the reals on
a (very dense line;-) is not the only model of looking at the reals,
and with less 'paradox': reals on [0,1) and in binary code: all
subsets 2^N of N, really are another data_type than the naturals
N=0{+1}*, namely sequentially generatable by 3 generators: group Z! .

And regarding GC, with the 'Euclidean' primesieve number notation:
it is not bitwise, but using a multi-base notation over the successive
primes: if m_k = \prod {first k primes}, then different from decimal
(or binary) code, use not the powers of _one_ base as moduli,
but successive m_k.  For instance the integers would start with:
          30 6 2 1   (digit weight)
m_0 = 1:         0         [next prime 2: digits 0,1 in first place]
                 1    (=1)
m_1 = 2:       1 0    (=2) [next prime 3: digits < 3 in second place]
               1 1    (=3)
               2 0    (=4)
               2 1    (=5)
m_2 = 6:     1 0 0    (=6) [next prime 5: digits < 5 in third place]
             1 0 1    (=7)
             1 1 0    (=8)
             1 1 1    (=9)
             1 2 0    (=10)
             1 2 1    (=11)
             2 0 0    (=12)
             2 0 1    (=13)
             . . .
             . . .
             4 2 1    (=29)
m_3= 30:   1 0 0 0    (=30) [next prime 7: digits < 7 in fourth place]
       etc...

Certainly the primes have more recognizable codes here, compared to
any single-base code. Would be interesting to persue... Any refs.?
--
Ciao, Nico Benschop -- http://piazza.iae.nl/users/benschop/cantor.htm
                       http://piazza.iae.nl/users/benschop/ism.htm
                       http://piazza.iae.nl/users/benschop/ng-abstr.htm

Re:      Dear Nico B. (Not Benschop) & 5 BSM
Author:  Nico Benschop
Date:   2000/05/19
Forum:  sci.math
---------

Jan Stevens (U-Chalmers, Sweden) wrote:
>
> In article <39226CB3.EF7B32ED@pop.hit.fi>,
>         Pertti Lounesto  writes:
> > Dear Nicolas Bourbaki,
>
> How many sci.math readers thought that this post concerned
> our Fermatist Nico B?

Typical PL-trick of mis-representation, cq out-of-context reference;-)
Moreover: Bourbaki was the epitome of 'abstract' method, I'm told,
while I prefer rather the very opposite: finite representation, and
an approach balancing objects & operations: semantics & syntax.
            ^^^^^^^^^ = BOOA Constructor =
                      = Balanced Object Oriented Algebra
BTW:
Not only am I a Fermat_ist, but also a Goldbach_er, and a Waring_er...

See http://www.iae.nl/users/benschop/nf-abstr.htm
    http://www.iae.nl/users/benschop/ng-abstr.htm
    http://www.iae.nl/users/benschop/nw-abstr.htm
    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   (redundant strings for lazy clickers;-)

All solved with the same 2-pronged method: finite semigroup Z(.) mod m
additively analysed qua structure, with modulus m chosen to fit the
problem:
m = p^k (prime p>2, k>1) for powersums [Fermat, Waring]
m = m_k = \prod first k>1 primes [Goldbach]:
     map all primes p between p_k and m_k into the units group at the
     top of the Boolean Lattice of 2^k groups, which Z(.) mod m_k is;
... followed by considering the carry (k>2) going global (integers>0).

In fact I'm interested, more generally, in a Digital Network Theory
which would allow to decompose any FSM (Finite State Machine) into
a network of the five basic State Machine (5 BSM) types ...
... unlike the rather 'cripple' Krohn-Rhodes ('65) decomposition into
permutation/reset machines: which uses only 2 of the 5 BSM's.

I suspect they (in the sixties) just generalized the Jordan/Hoelder
group decomposition theorem, by adding reset machines (basically:
flip-flops in case of binary code). Theory is complete but 'useless':
simulating the non-used other 3 component types with reset- and
permutation machines is NOT very efficient.
Hence the theory flopped for all practical purposes ;-(

The 5 BSM correspond to the 5 non-isomorphc semigroups of order 2:
with appealing computer engineering interpretations:
2: periodic & monotone counters (1 generator)
1: combinational logic gate (2 commuting ordered idempotents, AND isomorphic OR)
2: short & long memory (reset & branch, FF & mux, left & right copy sgrp)
                       (2 non-commuting idempotents)

And semigroups (finite associative) are the general model of
state- transformation closures = function composition.
    (you know: blocks coupled by input/output arrows;-)
http://www.iae.nl/users/benschop/c-ranksm.dvi (almost typed crank-sm;-)
http://de.arXiv.org/abs/math.GM/0103112 (all formats: .ps .pdf .dvi )

     "The structure of Constant Rank State Machines"
   IFIP workshop on "Logic & Architecture Synthesis"
   Paris, may'90.

> [...corrected Bourbaki of 39 years ago...]
> It would be really helpful for readers of Bourbaki if Lounesto
> pointed out which step of the proof in the original version
> is wrong. After all the case distinction dim E even or odd is
> made there.
> Groetjes (speciaal voor Nico) Jan

Bedankt Jan.
Nu ken ik (partially;-) eindelijk eens 1 van mijn ca. 3000 homepage
bezoekers (sinds jan98)...
--
Ciao, Nico Benschop -- http://www.iae.nl/users/benschop

    Re: On Hawking's method of thinking
Author: Nico Benschop
  Date: 2000/11/14
 Forum: sci.math
---------

freelancefabulous@my-deja.com wrote:
>
> I find that I can focus on a problem by sitting quietly (or lying in
> bed), and trying to find a tiny piece of a problem at a time. Not much
> point in trying to do it all at once. Then I let my brain sort of rock
> back and forth on the problem something like a hammock in the wind,
> sort of scanning possibilities.  Is this what other people do? -- FF

After getting to grips with the global 'nature' of a problem,
(in as spacy as possible but relevant context) you formulate
a question, and go to sleep. Let your subconcious 'work' on it
(essentially by associations & 'resonance' between similarities
- I guess), freed from your conscious/rational guidance &
eager-to-solve-it urge, and next morning: bingo, you (sometimes;-)
get a clue...

For instance: FLT is not so much about numbers (integers) but about
theoperations on them: only (^) and (+) occur in the statement, and
it's nature is "anti-closure" (the sum of two p-th powers is NOT a
p-th power)
So p-th powers are a good generating set for all naturals under (+).
Notice that (^) is defined as repeated (.), which is repeated (+).
Now (.) and (+) both are associative and commutative, while (^) is
neither, although it is just 'one step' beyond (.)... Strange eh?
For integers (^) does not distribute over (+), although for residues
there _are_ cases of (a+b)^p \eqv a^p + b^p (mod p^k), for instance
the cubic roots of unity: a^3 = 1 mod p^:  a + a^2 + 1 == 0 mod p^k,
if p=1 mod 6, so: a(a+1)== -1,
            resp: a(b+1)== b(c+1)== c(a+1)== -1 mod p^k. ('triplet')
Take it from there, using base p representation of numbers, since you
must prove inequality: how do you test two numbers to be different?
By checking their unique representation, here the relevant base is p,
the exponent: hence study residues semigroup Z(.) mod p^k,
              and especially its _additive_ structure;-)
http://www.iae.nl/users/benschop/anti-cl.htm
http://www.iae.nl/users/benschop/ferm.htm       /nf-abstr.htm

Second ex: Goldbach. Also an additive statement, this time about
another type of 'multiplicative' numbers, namely the primes:
mpy(.) basis of N. Here the best representation is over
m_k = product of the first k primes, and expand (induction) over k.
All primes < m_k are in the subgroup of residues mod m_k containing
unity 1,  except base-primes p_1,..p_k.
And look for some additive property of the idempotents ('invariants')...
Then  1 + 1    =  2       yields by equivalence 'association':
   unit + unit == even (mod m_k), and induction(k) + Bertrand Postulate:
    p_i + p_j  = 2n
http://www.iae.nl/users/benschop/ng-abstr.htm
http://www.iae.nl/users/benschop/fewago.htm

PS: Notice the two extremes acting here: 'sequential' modulus p^k
   (one prime p) and 'parallel' modulus m_k = \prod first k primes
(squarefree). This seems to 'span' all possibilities:
Fermat and Goldbach (both of additive nature) are about multiplicative
type nrs (n^p resp. primes p_i).
*** And eventually, function composition (associative, NOT commutative)
is the common context (=semigroups;-) for hard arithmetic problems...
    http://www.iae.nl/users/benschop/func.htm              --- NFB

Subject:  Re: characteristic of a field ?
   Date:  Thu, 13 Sep 2001 10:59:15 +0200
   From:  Nico Benschop
  Org'n:  Digital Research
Newsgrp:  sci.math, sci.crypt

Anton Stiglic wrote:
>
> > It's usefull to know the characteristic of a field when you are, for
> > example, dividing. Say you are working with polynomials over a field
> > F of char m, then you cannot do something like (x^2 -1) / m,  because
> > m = m*1 = 0 (because char of field is m), and you can't divide  by 0
> > (0 has no multiplicative inverse). --Anton
>
> NB:  Remarkable:
> this is the ONLY reply explaining what  "char F"  is good for!
>     (among the 13 knowledgeable replies that my ISP shows me;-)
> Does not that say a bit about math-teaching?
> How about motivation first, details second?     -- Just amazed, NB

> Jiandong Guo wrote:
> > This is a very stupid example since, well, m is just 0. I cannot
> > believe somebody even applaud for it. A better example which is
> > also highly trivial is to find (a + b + c)^ m where a, b , c are
> > elements of a finite field of characteristic p and p|m.
>
> m is the characteristic of the field, say for example 2.  2 != 0,
> 2 is a natural number, not an element of the field.  If I write
>       2*1, 2 in a natural number, 1 is an element of the field.
> 2*1 is simply short for 1 + 1.   m*1 is short for 1 + 1 .. + 1.
> This you learn in any basic group theory class.
>
> I have seen students do stuff like write  (x^2 + 1)/2*1
> and then simplify the denominator, in a Field with char 2.
> It might be obvious to you, but in a more complicated example
> it is sometimes unclear for students.  The example I gave was
> simple, but if you are not stupid you can understand how to
> apply it to more elaborate examples.
> A good teacher has 2 assets:
>   1)  know the material well,
>   2)  understand what students might have difficulty with.
> A lot of mathematicians have 1 but not 2,
> thus don't make for good teachers.
>
> Let me add an example often seen in introductory texts to elliptic
> curves.  [...]
> See for example page 22 of J. S Milne's elliptic curve class notes
> which you can get from  http://www.jmilne.org/math/
> Look also for Connell's draft of Elliptic Curve Handbook
> (on McGill's ftp site if I recall correctly).
> This IS an example which cryptographers might be interested in.
> --Anton

Thanks, most interesting.
  BTW: since you appear to know much about elliptic curves (EC),
the main field of research of Andrew Wiles - with the known 1995
result on EC = MF (modular form) - may I throw a question at you
regarding one corollary of that work (Annals of Mathematics,
the complete May issue '95) namely that Fermat's conjecture about
p-th power pairsums not yielding a p-th power for integers ("FLT")
is true. Altough I did not study the paper itself (I'm just an
interested amateur;-) I did read Simon Singh's book on Wiles' work.

The method of approach was explained to be via L-series
                      (Dirichlet jr.: 'Le Jeune' - hence the L ;-).
These count the number of solutions of a diophantine equation, but
in residues mod p (prime p) here a specific EC(a,b,c) mod p :
with (integer) coefficients a,b,c and a particular odd prime p.
This is done for all primes p_k (k=2-->inf) yielding, as it were, a
'spectrum' of values that characterizes that special EC. Same thing
is done with a modular form MF(a,b,c) with 'the same'(?) coefficients,
and voila: identical spectra show equality of that pair EC = MF.
Of course the proof must be set up to show equality for 'all'
coeficient triples {a,b,c}. - But OK, let this be done. ---

Notice this is a method of *residues*, albeit mod m_k,
in the limit k-->inf, where m_k = \prod {first k primes},
yet this does NOT establish anything about integers ("mod-free").

Now, just like an approach via residues mod p^k (prime exponent p
    in the FLT eqn), any residue method suffers from the known
   'Hensel Lift' (HL).  Which BTW is the main objection against a
'direct' proof of FLT by residues mod p^k (since equivalence mod p^2,
a necessary condition for any integer solution, can be extended to
mod p^k for k-->inf, 'never' yielding  equality for integers.

My question (to which I've not received any convincing answer yet,
and admittedly I'm not famliar with details of the FLT-corollary):

Q:  WHY does Wiles' L-series *residue* method NOT suffer from HL. ?!?

-- NB -- http://www.iae.nl/users/benschop/fewago.htm
         http://www.iae.nl/users/benschop/cubic.htm
         http://de.arXiv.org/abs/math.HO/0103051 :
(On Fermat's marginal note, a suggestion:
               the cubic roots of 1 mod p^2, p==1 mod 6, 'breaking' HL)