ALFREDO RIZZI - 21-st Century Breakthrough - AKS algorithm (primality test) is O log n
pamela fluente
Italian famous mathematician Alfredo Rizzi founds out that AKS
algorithm (primality test) is O log n
(In the process he also discovers that 1 is a prime number.)
http://rivista-statistica.cib.unibo.it/article/view/1291/697
Italian ingenuity ? Please comment the news.
Peter Fairbrother
Well I don't speak Italian so I don't know for sure if he's even worth
reading - but first clue, the English summary (at the end) doesn't say
he did either of those things.
I don't personally think the asymptotic complexity of AKS can be less
than O log^6 n, but I may be wrong, and it would be a big deal if it is
O log n.
I think his theorem 11 says that it is O log n, but the following 7
paragraphs most certainly do not contain anything which could possibly
be be a proof of that theorem.
After that he goes on about probabilistic tests in section 4, so he's
not talking about AKS any more.
So no, he didn't prove AKS is O log n.
Whether 1 is prime is a matter of a point of view and how you define a
prime, rather than mathematics. Most people use the useful POV that 1
isn't prime, and also 1 isn't composite, as it behaves in a manner
different to primes or composite numbers.
So it would not even be possible to prove that 1 is prime.
He did neither.
-- Peter Fairbrother
pamela fluente
> pamela fluente wrote:
> > After cold fusion, another 21-st Century Breakthrough.
>
> > Italian famous mathematician Alfredo Rizzi founds out that AKS
> > algorithm (primality test) is O log n
> I don't personally think the asymptotic complexity of AKS can be less
> than O log^6 n, but I may be wrong, and it would be a big deal if it is
> O log n.
>
> So no, he didn't prove AKS is O log n.
>
Well you dont seem to get the point.
What do you think your opinion would matter ? Who are you ?
Don't you see that Prof. Alfredo Rizzi is listed among the great
mathematicians of this century: ??
http://felix.unife.it/Root/d-Mathematics/d-The-mathematician/t-Mathematicians-A-Z
Is your name also in this list ? How do you dare to object ?
He is also one of the world foremost expert in cryptography:
http://www.libreriauniversitaria.it/cifrari-codici-segreti-rizzi-alfredo/libro/9788843054374
I did not dare read the book because it could blow my mind, but If he
says that AKS is O^log n
(or was that O(logn) ?? , whatever! ) we must believe him because he
is such a genius and also so famous.
Well ok he doesn not know that the current prime definition does not
contain 1. He cannot tell the difference between primes and coprimes.
He think that "Safena" is an author of AKS (and not a vein). He cannot
spell Riemann and Adleman. So what ?
He writes in the summary:
"He remembers the very important researches of Eulero, Fermat, Legen-
re, Rieman and others scholarships"
So what ? Anything to object with scholarships? How you dare doubt the
ingenuity of this famous mathematician,
A Full professor of the University of Rome publishing on such a top
journal such breakthrough,
a journal where also have published geniuses such as Mary Fraire and
Paola Monari ?
I think you don't have read carefully and understood none of the gems
this paper
brings to the scientific community.
-Pam
Peter Fairbrother
> On 5 Giu, 19:05, Peter Fairbrother <zenadsl6...@zen.co.uk> wrote:
>> pamela fluente wrote:
>>> After cold fusion, another 21-st Century Breakthrough.
>>> Italian famous mathematician Alfredo Rizzi founds out that AKS
>>> algorithm (primality test) is O log n
>> ...
>> I don't personally think the asymptotic complexity of AKS can be less
>> than O log^6 n, but I may be wrong, and it would be a big deal if it is
>> O log n.
>>
> ...
>> So no, he didn't prove AKS is O log n.
>>
>
>
> Well you dont seem to get the point.
> What do you think your opinion would matter ? Who are you ?
>
> Don't you see that Prof. Alfredo Rizzi is listed among the great
> mathematicians of this century: ??
>
> http://felix.unife.it/Root/d-Mathematics/d-The-mathematician/t-Mathematicians-A-Z
>
> Is your name also in this list ? How do you dare to object ?
>
> He is also one of the world foremost expert in cryptography:
> http://www.libreriauniversitaria.it/cifrari-codici-segreti-rizzi-alfredo/libro/9788843054374
Oh no he isn't!
I found this:
http://www.datatime.eu/public/geniuses/AlfredoRizzi_PrimalityTests.htm
(I suspect you found it too :)
when looking for papers he had written. Seems he edited a volume of
conference proceedings once, but as far as citeseer goes, that's it -
seems he has no well-established published original work at all.
Even the paper you refer to isn't in citeseer ...
But that sort of thing happens in academia in other places than in
Italy. People who don't deserve promotion or tenure get it because of
who they know or for other academic political reasons. If you can bring
in a lot of money, that helps, for instance.
It's not usually so blatant though. One popular trick he missed is to
have the papers so complex that no-one can possibly understand what they
say, and then no-one can contradict you.
-- Peter Fairbrother
(not in academia, thank goodness. But I am in citeseer, as an author :)
pamela fluente
> pamela fluente wrote:
>
> > ...
> >> So no, he didn't prove AKS is O log n.
>
> > Don't you see that Prof. Alfredo Rizzi is listed among the great
> > mathematicians of this century: ??
>
>
> > Is your name also in this list ? How do you dare to object ?
>
> > He is also one of the world foremost expert in cryptography:
>
> Oh no he isn't!
>
> I found this:http://www.datatime.eu/public/geniuses/AlfredoRizzi_PrimalityTests.htm
>
> (I suspect you found it too :)
>
> when looking for papers he had written. Seems he edited a volume of
> conference proceedings once, but as far as citeseer goes, that's it -
> seems he has no well-established published original work at all.
>
> Even the paper you refer to isn't in citeseer ...
>
> But that sort of thing happens in academia in other places than in
> Italy. People who don't deserve promotion or tenure get it because of
> who they know or for other academic political reasons. If you can bring
> in a lot of money, that helps, for instance.
>
> It's not usually so blatant though. One popular trick he missed is to
> have the papers so complex that no-one can possibly understand what they
> say, and then no-one can contradict you.
ahah right!
Well, for that you need some brain, though!
>
> -- Peter Fairbrother
>
> (not in academia, thank goodness. But I am in citeseer, as an author :)
>
I am sure you do :-)
-Pam
Peter Fairbrother
According to your famous mathematicians link, he was born in 1933, so
he'd be about 78 now - maybe he just got less discriminating as he got
older.
But for a professor, especially an older one, not to have any papers
cited in citeseer, especially a statistics professor, is - unusual.
-- Peter F
pamela fluente
>
> According to your famous mathematicians link, he was born in 1933, so
> he'd be about 78 now - maybe he just got less discriminating as he got
> older.
>
> But for a professor, especially an older one, not to have any papers
> cited in citeseer, especially a statistics professor, is - unusual.
>
> -- Peter F
Well, when you don't have your own original ideas, and all you can do
is copy paste from other sources,
without even understanding the significance and dept of the results
you are quoting,
adding your meaningless superficial remarks, based on what "you think"
you have understood,
it not so easy to get published in decent journals, which are not run
by close friends (clearly
of the same "scientific" level, provided we can talk of science in
this case).
But you can still write books (God save us) !
http://www.ibs.it/libri/rizzi+alfredo/libri+di+alfredo+rizzi.html
-Pam
Pubkeybreaker
Although I do not read Italian, I can follow the mathematics.
This paper contains no proofs or derivations that show AKS
is O(log(n)). Indeed, it contains no derivations for the time
complexity
of AKS at all.
Allow me to point out that JUST WRITING DOWN the candidate for
testing takes O(log(n)). Furthermore, the most efficient known
algorithm for primality testing is the LL algorithm for Mersenne
primes.
It takes O(log(n)) MULTIPLCATIONS mod n. It is O(log^2 n loglog
n)
using FFT's for the multiplication.
AKS works (basically) by proving a lower bound on the size of the
largest cyclic subgroup of Z/nZ*. It would be astonishing if this
could be done in O(log n) time. Indeed; if one gives a factorization
of
a composite, just verifying the factorization (not deriving it, but
just verifying)
can't be done in time O(log(n)).
I would be happy to referee this paper if someone can provide an
English (or even
French) translation.
We can't even multiply two n-bit numbers together in time O(n) on a
Turing machine.
Pubkeybreaker
>
> So no, he didn't prove AKS is O log n.
>
> Whether 1 is prime is a matter of a point of view
I don't know any number theorists who think 1 is a prime.
Pubkeybreaker
> On 5 Giu, 19:05, Peter Fairbrother <zenadsl6...@zen.co.uk> wrote:
>
> > pamela fluente wrote:
> > > After cold fusion, another 21-st Century Breakthrough.
>
> > > Italian famous mathematician Alfredo Rizzi founds out that AKS
> > > algorithm (primality test) is O log n
> > ...
> > I don't personally think the asymptotic complexity of AKS can be less
> > than O log^6 n, but I may be wrong, and it would be a big deal if it is
> > O log n.
>
> ...
> > So no, he didn't prove AKS is O log n.
>
> Well you dont seem to get the point.
> What do you think your opinion would matter ? Who are you ?
I read the paper and my opinion does matter.
>
> He is also one of the world foremost expert in cryptography:http://www.libreriauniversitaria.it/cifrari-codici-segreti-rizzi-alfr...
Sorry, but no.
>
> I did not dare read the book because it could blow my mind, but If he
> says that AKS is O^log n
> (or was that O(logn) ?? , whatever! ) we must believe him because he
> is such a genius and also so famous.
Mathematics is not done this way. If he shows us a proof of his
claim,
we can verify it for ourselves. His paper contains no proof or
derivation.
> So what ? Anything to object with scholarships? How you dare doubt the
> ingenuity of this famous mathematician,
I hope that you are being facetious........
Peter Fairbrother
Well no, neither do I.
:)
From Mathworld:
http://mathworld.wolfram.com/PrimeNumber.html
The number 1 is a special case which is considered neither prime nor
composite (Wells 1986, p. 31).
Although the number 1 used to be considered a prime (Goldbach 1742;
Lehmer 1909, 1914; Hardy and Wright 1979, p. 11; Gardner 1984, pp.
86-87; Sloane and Plouffe 1995, p. 33; Hardy 1999, p. 46), it requires
special treatment in so many definitions and applications involving
primes greater than or equal to 2 that it is usually placed into a class
of its own.
A good reason not to call 1 a prime number is that if 1 were prime, then
the statement of the fundamental theorem of arithmetic would have to be
modified since "in exactly one way" would be false because any n=n·1. In
other words, unique factorization into a product of primes would fail if
the primes included 1.
A slightly less illuminating but mathematically correct reason is noted
by Tietze (1965, p. 2), who states "Why is the number 1 made an
exception? This is a problem that schoolboys often argue about, but
since it is a question of definition, it is not arguable."
As more simply noted by Derbyshire (2004, p. 33), "2 pays its way [as a
prime] on balance; 1 doesn't."
-- Peter Fairbrother
Pubkeybreaker
> On 6 Giu, 17:16, Pubkeybreaker <pubkeybrea...@aol.com> wrote:
>
>
>
> > I hope that you are being facetious........- Nascondi testo citato
>
> Just sad irony. Unfortunately there isn't much to laught about. These
> are people who
> dont care destroying other people lives and destroying real talent or
> dedication, in the attempt to reduce the world to their level.
>
> Anyway, talking of real science, it captured me your statement (if i
> correcly undestood)
> that just to set up the number for testing, we already "burn" log n.
You have to read (or otherwise insert) the number into memory!
It has O(log n) bits to read in!!!!
> Computational complexity really fashinates me, but i still have some
> (actually many) doubts.
About what? Perhaps I can clarify things.
>
> Since you are here :-) , one or some questions. Assume i had to write
> a paper where a present a new algorithm (eg, factoring or testing).
>
> Do I have to include in the time computations even the input time of
> the numbers
> or it is kept out of the time computations ? What is the proper way
> (or rule) ?
For a new algorithm?? One definitely needs an analysis of the run
time.
Input time does not matter. If an algorithm is O(log^2 n) and the
input time is
O(log n), the latter is majorized by the former. O(log^2 n + log n) =
O(log^2 n)
>
> Also what is more "correct", working with n as the actual number (for
> instance being factored or tested), or with the number of digits ?
Algorithm run time is typically given in terms of bit complexity, but
it
really doesn't matter. One can express the result in terms of
log(n)
or in terms of the number of digits, or in terms of the number of
bits.
They are all the same. e.g. let ln denote natural log. Then ln(x)
= O(log(x))
where log is base 10 log........They only differ in the implied
constant
in the O() estimate.
May I suggest that you read a book on complexity analysis? I can
recommend
some good ones.
> I can imagine we can easily pass from one to another
>since the number
> of digits are in the order of log,
Yep!
>but just curious about
> what would be considered best from the field experts.
There is no "best". It is merely a matter of notational convenience
and writing style.
>
> Also why when talking about arrays we can say that a loop for i=0,,,n
> (containing for instance 10 multiplications)
> has time O(n) and we dont care about the intermediate operations.
It depends on what operations take place within the loop.
And if multiplications are in the loop, then the length of the
operands
DOES matter if one counts bit operations.
Or, one can just count 32-bit arithmetic operations, absorbing the
bit-level complexity into a 'word-level' complexity. The run time
complexity
will be the same except for a constant factor that is covered by the
big-oh
notation anyway.
>Or
> we normally say we can get a value from an hastable
> in O(1) [eghttp://www.cs.auckland.ac.nz/~jmor159/PLDS210/hash_tables.html
> ]. Is this another kind of convention ??
Table lookup is a different kind of operation. Table lookup can not
be done
in time O(1) because this would assume one was working on a pointer
machine [a machine where any piece of memory can be accessed in
constant
time, which is clearly not true for current computers; the bigger the
table, the more
memory is needed. Geometry requires that the more memory one has, the
farther
away it must be physically from the CPU. Now consider speed-of-light
limitations]
Real world computers are not pointer machines. Neither are Turing
machines --> To
access e.g. a memory square that is at distance 'D' from the square
under the current
pointer requires that we traverse D locations. This takes time
O(D).
Time is not the only complexity measure of an algorithm. Space is
also a major
requirement and many algorithms can make time/space tradeoffs.
>
> From the discussions i have followed so far, it's like there were 2
> different framework, one used by number theory experts, and
> one used by computer scientists (??).
Not as I see it.
Pubkeybreaker
> Pubkeybreaker wrote:
> > On Jun 5, 1:05 pm, Peter Fairbrother <zenadsl6...@zen.co.uk> wrote:
> >> pamela fluente wrote:
> > not talking about AKS any more.
> >> So no, he didn't prove AKS is O log n.
>
> >> Whether 1 is prime is a matter of a point of view
>
> > I don't know any number theorists who think 1 is a prime.
>
> Well no, neither do I.
>
> :)
>
> From Mathworld:
>
> http://mathworld.wolfram.com/PrimeNumber.html
>
> The number 1 is a special case which is considered neither prime nor
> composite (Wells 1986, p. 31).
1 is a UNIT.... (an element of a ring for which a multiplicative
inverse
exists)
>
> A good reason not to call 1 a prime number is that if 1 were prime, then
> the statement of the fundamental theorem of arithmetic would have to be
> modified since "in exactly one way" would be false because any n=n·1. In
> other words, unique factorization into a product of primes would fail if
> the primes included 1.
BINGO!
This is the primary reason (pun intended)
pamela fluente
> You have to read (or otherwise insert) the number into memory!
> It has O(log n) bits to read in!!!!
ok
> For a new algorithm?? One definitely needs an analysis of the run
> time.
>
> Input time does not matter. If an algorithm is O(log^2 n) and the
> input time is
> O(log n), the latter is majorized by the former. O(log^2 n + log n) =
> O(log^2 n)
ah ok. But anyway we dont have to even mention the input, Right ?
> They are all the same. e.g. let ln denote natural log. Then ln(x)
> = O(log(x))
> where log is base 10 log........They only differ in the implied
> constant
> in the O() estimate.
well, the "same". I can see in exp() appearing when dealing with
digits. Same in the sense that we can easily pass from one to another
because #digits = [log(n)] + 1 or what do you mean exactly ?
>
> May I suggest that you read a book on complexity analysis? I can
> recommend
> some good ones.
sure i'd like to know the more viable and precise references
> >Or
> > we normally say we can get a value from an hastable
> > in O(1) [eghttp://www.cs.auckland.ac.nz/~jmor159/PLDS210/hash_tables.html
> > ]. Is this another kind of convention ??
>
> Table lookup is a different kind of operation. Table lookup can not
> be done
> in time O(1) because this would assume one was working on a pointer
> machine [a machine where any piece of memory can be accessed in
> constant
> time, which is clearly not true for current computers; the bigger the
> table, the more
> memory is needed. Geometry requires that the more memory one has, the
> farther
> away it must be physically from the CPU. Now consider speed-of-light
> limitations]
hmmm here still something not clear. Why they always say O(1)
for instance:
http://stackoverflow.com/questions/2565455/what-is-the-complexity-of-ordereddictionary
in all documentation i read i always found mentioned these O(1)
accesses
and this is a little puzzling
>
> Real world computers are not pointer machines. Neither are Turing
> machines --> To
> access e.g. a memory square that is at distance 'D' from the square
> under the current
> pointer requires that we traverse D locations. This takes time
> O(D).
If D is a constant, that would not be noted still as O(1) ?
>
> Time is not the only complexity measure of an algorithm. Space is
> also a major
> requirement and many algorithms can make time/space tradeoffs.
Yep that sound very interesting. I think i have heard about time
complexity most of time.
In which type of algorithm is space important, maybe more than time ?
-P
pamela fluente
>
> AKS works (basically) by proving a lower bound on the size of the
> largest cyclic subgroup of Z/nZ*. It would be astonishing if this
> could be done in O(log n) time. Indeed; if one gives a factorization
> of
> a composite, just verifying the factorization (not deriving it, but
> just verifying)
> can't be done in time O(log(n)).
>
very interesting.
Assuming, as we are doing, that n is the actual number being
factorized,
what is the best time to just verify that for 3 given integer we
have :
f1 * f2 = n
and how is this best time achieved ?
Also, what is the "theoretical lowest bound" (in terms of computing
time)
for a factoring algo ?
-Pam
Pubkeybreaker
> On 6 Giu, 18:58, Pubkeybreaker <pubkeybrea...@aol.com> wrote:
>
>
> ah ok. But anyway we dont have to even mention the input, Right ?
It depends on the complexity of the algorithm.
>
> > They are all the same. e.g. let ln denote natural log. Then ln(x)
> > = O(log(x))
> > where log is base 10 log........They only differ in the implied
> > constant
> > in the O() estimate.
>
> well, the "same". I can see in exp() appearing when dealing with
> digits. Same in the sense that we can easily pass from one to another
> because #digits = [log(n)] + 1 or what do you mean exactly ?
I don't understand what you are asking.
>
>
>
> > May I suggest that you read a book on complexity analysis? I can
> > recommend
> > some good ones.
>
> sure i'd like to know the more viable and precise references
Aho, Hopcroft & Ullman's book on Algorithms gives a gentle and
excellent exposition.
> hmmm here still something not clear. Why they always say O(1)
> for instance:http://stackoverflow.com/questions/2565455/what-is-the-complexity-of-...
They are assuming that their tables have fixed size and do not depend
on the
size of the inputs.
>
> in all documentation i read i always found mentioned these O(1)
> accesses
> and this is a little puzzling
They are assuming bounded inputs.
Consider instead, doing multiplication on two n-bit numbers via
table lookup. How big do the tables need to be?
> > Real world computers are not pointer machines. Neither are Turing
> > machines --> To
> > access e.g. a memory square that is at distance 'D' from the square
> > under the current
> > pointer requires that we traverse D locations. This takes time
> > O(D).
>
> If D is a constant, that would not be noted still as O(1) ?
But it typically will NOT be a constant. It will depend on the size
of the inputs.
>
Pubkeybreaker
> On 6 Giu, 17:12, Pubkeybreaker <pubkeybrea...@aol.com> wrote:
> >
>
> > AKS works (basically) by proving a lower bound on the size of the
> > largest cyclic subgroup of Z/nZ*. It would be astonishing if this
> > could be done in O(log n) time. Indeed; if one gives a factorization
> > of
> > a composite, just verifying the factorization (not deriving it, but
> > just verifying)
> > can't be done in time O(log(n)).
>
> very interesting.
>
> Assuming, as we are doing, that n is the actual number being
> factorized,
> what is the best time to just verify that for 3 given integer we
> have :
>
> f1 * f2 = n
>
> and how is this best time achieved ?
Multiply f1 and f2, then compare. If each has n bits, the time is
n log n loglog n.
>
> Also, what is the "theoretical lowest bound" (in terms of computing
> time)
> for a factoring algo ?
A non-deterministic TM can do it in the time given above. Noone knows
the answer for determinstic TM. We do have an upper bound.
pamela fluente
> > > They are all the same. e.g. let ln denote natural log. Then ln(x)
> > > = O(log(x))
> > > where log is base 10 log........They only differ in the implied
> > > constant
> > > in the O() estimate.
>
> > well, the "same". I can see in exp() appearing when dealing with
> > digits. Same in the sense that we can easily pass from one to another
> > because #digits = [log(n)] + 1 or what do you mean exactly ?
>
> I don't understand what you are asking.
ok.
Let make a practical example.
Let's take the f1 * f2 = n you just gave the interesting complexity
as:
"If each has n bits, the time is n log n loglog n".
Now assume we want to express the SAME complexity in terms
of the actual given numbers f1, f2, n.
How would that change ?
And why there is an implied "constant", isnt log (n) still depending
on the input size
or is that "absorbed" in the expression ?
>
>
>
> > > May I suggest that you read a book on complexity analysis? I can
> > > recommend
> > > some good ones.
>
> > sure i'd like to know the more viable and precise references
>
> Aho, Hopcroft & Ullman's book on Algorithms gives a gentle and
> excellent exposition.
thanks a lot. Is that the "introduction to automata" ? I will get it
>
> Consider instead, doing multiplication on two n-bit numbers via
> table lookup. How big do the tables need to be?
hmm, would i not precompute first the table, and use the
table limits as precondition of the multiplication ?
Or do you mean that the "cross table" of products would be created
everytime before multiplication ?
-Pam
Tom St Denis
Keeping in mind that the FFT algorithm only really applies to really
large numbers because there is an enormous constant that goes with
that work that isn't present in Karatsuba or straight up Comba based
multiplication.
Tom
Pubkeybreaker
> On 6 Giu, 23:44, Pubkeybreaker <pubkeybrea...@aol.com> wrote:
> Let make a practical example.
>
> Let's take the f1 * f2 = n you just gave the interesting complexity
> as:
>
> "If each has n bits, the time is n log n loglog n".
>
> Now assume we want to express the SAME complexity in terms
> of the actual given numbers f1, f2, n.
>
> How would that change ?
I just noticed that my use of n duplicates the 'n' in the problem
statement.
I redefined n.
The complexity of multiplying two n-bit numbers is O( n log n loglog
n)
For the above multiplication, let m = log_2(n) [number of bits in
n]
Then the size of f1 = m/2 and size of f2 = m/2. The complexity of
verifying the product is O(m log m loglog m) as I stated before.
Why is
this hard? The number of bits (also known as the size) in a number
is
just its logarithm. This is trivial.
>
> And why there is an implied "constant", isnt log (n) still depending
> on the input size
> or is that "absorbed" in the expression ?
You seem not to understand O() notation. Explanations are
readily available over the Internet, but I will give one here.
A function f (of a free variable x) is said to be O(g(x)) if
|f(x)|/|g(x)| < k for all x > M, for some suitable values of k
and M.
In other words, f(x) grows no faster than a fixed multiple of g(x)
for all
suitably large x. The value of 'k' is the implied constant.
> > Aho, Hopcroft & Ullman's book on Algorithms gives a gentle and
> > excellent exposition.
>
> thanks a lot. Is that the "introduction to automata" ? I will get it
>
No. They have a separate book on algorithms in addition to their
Automata book.
>
>
> > Consider instead, doing multiplication on two n-bit numbers via
> > table lookup. How big do the tables need to be?
>
> hmm, would i not precompute first the table, and use the
> table limits as precondition of the multiplication ?
Huh? I asked a simple question. In order to multiply two n-bit
numbers
by table lookup, how big does the table need to be??? I will give a
hint:
It is not fixed in size. The size is a function of n. Thus, the
table lookup
can not be O(1) since the size of the table depends on n.
>
> Or do you mean that the "cross table" of products would be created
> everytime before multiplication ?
It needs to be done only once *if* you can bound n.
But it still remains that the size of the table is a function of n.
The time to
access that table is thus a function of n. Suppose you have two
instances
of the table. One is for a program to multiply 32 bit-integers;
Another is to
multiply 64 bit integers. The second table is much larger and takes
longer to access.
(note that BOTH tables are very very large);
Table lookup is O(1) if and only if the size of the table does not
depend on the
size of the problem being solved.
>
> -Pam
Bryan
> Peter Fairbrother wrote:
> > The number 1 is a special case which is considered neither prime nor
> > composite (Wells 1986, p. 31).
>
> 1 is a UNIT.... (an element of a ring for which a multiplicative
> inverse
> exists)
>
> > A good reason not to call 1 a prime number is that if 1 were prime, then
> > the statement of the fundamental theorem of arithmetic would have to be
> > modified since "in exactly one way" would be false because any n=n·1. In
> > other words, unique factorization into a product of primes would fail if
> > the primes included 1.
>
> BINGO!
>
> This is the primary reason (pun intended)
And then zero needs a class of its own. While zero is easy to factor
-- any multiset that contains zero at least once is a factorization of
zero -- it cannot be expressed as a product of primes, and is no unit
as it lacks a multiplicative inverse.
Prime, composite, unit, and zero... Are we there yet?
--
--Bryan
pamela fluente
About the list of "famous mathematicians",
while we understand that the mediocrity need self-referencing for its
unjust means,
i'd suggest that the names of the actual mathematicians would be
removed
and the list title changed into "people who think they are famous"
After this discussion, and considering the appearance on the media,
this great full professor (also noted for his intellectual honesty:
http://socialeanimale.wordpress.com/2008/11/16/la-mafia-accademica-gli-imbrogli-nelle-universita-italiane/
) might be considereded reasonably "famous".
Other proposals ?
Pubkeybreaker
> About the list of "famous mathematicians",
>
> while we understand that the mediocrity need self-referencing for its
> unjust means,
>
> i'd suggest that the names of the actual mathematicians would be
> removed
>
> and the list title changed into "people who think they are famous"
Who put together this list??? Your comment seems to imply that you
believe people placed themselves (inappropriately) on the list.
What is meant by "famous" in this context?
If one were to grab 1000 people off the street and ask them to name
even (say) 5 famous mathematicians, I doubt whether responses
would be forthcoming.
Mathematicians are almost totally unknown to everyone except
other mathematicians (and physicists).
Phoenix
I apologize for interfering.
I fully agree with you, Pubkeybreaker, very few know the names of
great mathematicians, especially in the last two centuries.
If I ask, who was Albert Einstein, many people know who did it.
But if I ask who was Henri Poincaré, 'nobody' knows.
Jeffrey Goldberg
> Mathematicians are almost totally unknown to everyone except
> other mathematicians (and physicists).
And this is why we go on publication record as a proxy.
Pamela,
There are lots of people who contribute greatly to mathematics by being
great teachers, or by working to provide an environment in which
mathematicians thrive. There there are lots of ways to be a good person
without contributing to mathematics. Nobody here is judging Alfredo
Rizzi as a person. But he shows no indication of being a great
mathematician.
I didn't try to read the paper. Partially because I don't know any
Italian and I'm not particular competent to judge work in that area. But
mostly it was because your post had that silly statement about proving
that 1 is a prime number.
As has been pointed out, that is not a matter of proof, but a matter of
definition. It isn't, however, arbitrary. The Fundamental Theorem of
Arithmetic (and many other things) just don't work if we define 1 as
prime (or composite).
The one thing that works with 1 defined as a prime number is a joke we
told in graduate school (I'm a Phd Drop-out in Linguistics):
Bob hears the rumor that all odd numbers are prime, so he first goes to
a mathematician for confirmation.
Mathematician: Let p, q > 1 be odd. p*q is odd and composite. Thus the
conjecture is false.
Bob figures that he can never understand mathematicians so he decides he
needs to go to someone who uses these numbers, and goes to a physical
chemist.
P Chemist: Well, 1 is prime, 3 is prime, 5 is prime, 7 is prime, 9 well
uh, 11 is prime, 13 is prime. Sure they are all prime. We just had some
experimental error around 9.
Bob isn't quite convinced by this, and so he goes to the engineer.
Engineer: 1 is prime, 3 is prime, 5 is prime, 7 is prime, 9 is prime,
11, is prime, 13, is prime, 15 is prime, 17 is prime, ...
The engineer is still counting as Bob walks away. [This is where the
original joke ended, but we added a few bits]
So Bob goes to artificial intelligence researcher.
AI Researcher: That's a simple question. I'll code this up quickly and
we will have our answer. It will just take a few minutes.
Ten hours later when the code compiles, it comes back with: 1 is prime,
3 is prime, 5 is prime, 7 is prime, 7 is prime, 7 is prime, 7 is prime,
7 is prime, 7 is prime, ...
Bob leaves the AI researcher and figures he should talk to some of these
newfangled linguists. They know something about math, but should be able
to actually talk to people. So he meanders down to building 20 and finds
a man ranting about politics and poses the conjecture.
Linguist: 1 is prime. Yes, it must be a universal property of odd numbers.
Cheers,
-j
--
Jeffrey Goldberg http://goldmark.org/jeff/
I rarely read HTML or poorly quoting posts
Reply-To address is valid
pamela fluente
>
> Mathematicians are almost totally unknown to everyone except
> other mathematicians (and physicists).
When one makes a list of people famous in a field, it's understood
that
they are "famous" relative to the persons who know something about the
field.
This is obvious.
We are not talking of "popularity".
I think that for most people reading here, names like Gauss and Euler
are "famous mathematicians", (in addition to being natural geniuses).
Or, better, "great" mathematicians.
Recently, names like Wiles and Perelman also become famous (and also
"popular").
Larry King might be "popular", but probably we don't consider him a
famous mathematician.
I dont think a mathematician cares to be famous with housewives. We
aspire to being famous for creating or finding something
intellectually beautiful.
It might also happen that there are some "media scientists" (we have
here personalities like Zichichi or Odifreddi, etc.) who can be though
very low (or completely despised) by their (supposed) peers.
Well, about not knowing the name of people Einstein, that would be
matter of pure ignorance. Further, probably E. did not even consider
himself a "mathematician" (in the sense understood by masses) ...
-Pam
pamela fluente
:-)) very funny story. Thanks for sharing.
I might add a philosopher:
Primes are like the "fundations" of integers.
From each prime an entire "descendance" stems (as multiples). And
where "holes" remain, a new "prime" rises, to fill up and start a new
"descendance".
1 would not create anything and remain "still" and immutable in its
"reflective narcisism". It's single lonely guy who just decided not to
perpetuate himself, but to stare at himself. So its "prime" to
nothing...
;-))
-Pam
kg
>Pamela, [...]
In this conversation, I see one Italian making fun of an Italian
professor, implying that he is incompetent. And I see many non-Italians
earnestly arguing that this professor doesn't seem so hot.
Am I misreading this conversation?
--
kg
pamela fluente
you certainly are.
We are discussing about a scientific paper, published on a scientific
journal.
The paper speaks for itself. As it was published - after the author
carefully proofread it
and the referees of the journal reviewed it - now it belongs to the
public, and can be discussed.
-P
Jeffrey Goldberg
I so hope you are right!
I would be very pleased to know that I've been barking up the wrong
tree. Still, I did get to tell an old joke about prime numbers, so I had
fun with it anyway.