jump to navigation

Previously unpublished manuscript by Boris Weisfeller March 19, 2012

Posted by Alexandre Borovik in Uncategorized.
add a comment

Boris Weisfeiler, On the size and structure of finite linear groups,  http://arxiv.org/abs/1203.1960

This is a nearly complete, previously unpublished manuscript by Boris Weisfeiler. The results were announced by him in August 1984. Soon after, in early January 1985, he disappeared during a hiking trip in Chile.

The investigation into Boris Weisfeiler disappearance is still ongoing in Chile, see http://www.weisfeiler.com/boris

Advertisements

Monsieur, x^p = x (mod p), donc Dieu existe. Repondez! March 12, 2011

Posted by Alexandre Borovik in Uncategorized.
13 comments

I took liberty of copying it from Foundations of Mathematics Digest. A post by Daniel Mehkeri:

Monsieur, x^p = x (mod p), donc Dieu existe. Repondez !

In _Constructivism in Mathematics_, Troelstra and van Dalen
famously write,

…we do accept that “in principle” we can view 1010^10 as a sequence of units (i.e. we reject the ultrafinitist objection), and the authors are not sure that this is really less serious than the platonist extrapolation. At least it needs arguments.

I would like to make such an argument. I think it is new: at least, a shallow search fails to turn anything up where it ought to have been mentioned. Ultrafinitism certainly gets discussed a fair bit
on FOM for instance, but I saw nothing in the archives about this, other than my own vague statement last May to the effect that modular exponentiation will be problematic for the ultrafinitist,
which is what I would like to expand on.

THEOREM (Fermat). If p is prime, x^p = x (mod p). 
PROOF: Consider the set of all sequences of length p of symbols from an alphabet of size x. Its size is x^p. The number of distinct cyclic permutations of a given sequence divides p. But p is prime, so either there are p of them, or just one. In the latter case the sequence will consist of p repetitions of the same letter. There are x distinct cases of this. So the remaining x^p – x sequences are partitioned into orbits of size p. So p divides x^p – x, so x^p = x (mod p). QED

This is a very nice proof. But can it really be valid, except for small p? Consider the case of p=1031, x=2: we have to consider the set of _all_ binary sequences of length 1031. There would be far more sequences than Planck-time-by-Planck-volumes in the entire history of the observable universe from the big bang to the estimated death of the last star. Some would call that mysticism.

Now, it might be thought there could be an alternate ultrafinitary proof. Here is a reason to think otherwise: suppose for example Bounded Arithmetic could prove it. Then we could extract a
polynomial-time algorithm which, given x and p such that x^p =/= x (mod p), finds a non-trivial divisor of p. But no such algorithm is known. This isn’t definitive (if I could _prove_ there was no
such algorithm, I’d be rich) but it is doubtful that any exist.

This doesn’t just apply to BA and to the idea that feasibility means PTIME. It is enough to know that there is no known algorithm for factoring large numbers which is feasible in any sense, while modular exponentiation is well within current technology. We can easily code up a computer program to check that indeed x1031 = x (mod 1031) for all 0<=x<1031. Or even that 2^p =/= 2 (mod p) when

p = 25195908475657893494027183240048398571429282126204032027777137
83604366202070759555626401852588078440691829064124951508218929
85591491761845028084891200728449926873928072877767359714183472
70261896375014971824691165077613379859095700097330459748808428
40179742910064245869181719511874612151517265463228221686998754
91824224336372590851418654620435767984233871847744479207399342
36584823824281198163815010674810451660377306056201619676256133
84414360383390441495263443219011465754445417842402092461651572
33507787077498171257724679629263863563732899121548314381678998
85040445364023527381951378636564391212010397122822120720357,

so that, by theology, we know p is composite. But nobody knows a factor [see Wikipedia, “RSA Factoring Challenge”]. “p is composite” is a Delta_0 sentence (Sigma^b_1 in bounded quantifiers), for which we have a constructive proof, but no known ultrafinitary proof.

Notice what happens. Or rather, what doesn’t.

For p < 32, everything is just fine.

For p on the order of 210, the proof is problematic because “the set of all sequences of length p” is too big. But we can check all cases by direct computation.

For p on the order of 264, the idea of even a single “sequence of length p” is now doubtful, being at the edge of current storage techonology. And we can’t hope to check all cases. But it is still feasible to directly check whether any given p is prime, and to check the equation for any given x,p pair in this range.

For p on the order of 22^10, “the set of all sequences of length p” ought to be empty. There are no such sequences in reality! Yet we can still check any given x,p pair. It is tricky to check whether a given p really is prime without circularly resorting to theological number theory. But there are still ways to go about it. In fact, there is already lots of evidence at this level, in that much of modern cryptography depends on Fermat’s little theorem for numbers of this size, and it works!

Of course none of the above is statistically significant with respect to the Pi_1 theorem, but that’s not the point. The problem for ultrafinitism is, as I say, already Delta_0: why should it be right even in most of these cases, never mind be infallible? (There is no probabilistic feasible algorithm to factor large numbers, either.) Also, why is there no sign of the difference between feasible and
infeasible?

Because from an ultrafinitist perspective, the numbers in these levels are qualitatively different. Certainly our ability to check the statement changes drastically. And yet, there is no hint of any
ontological change. Nothing at all happens to Fermat’s little theorem, even up to x^p = 22^210.

The constructivist simply affirms that Elementary Recursive Arithmetic is TRUE; God made the integers, as Kronecker said. The ultrafinitist has some explaining to do. If these are just our collective delusions and meditations about entities that can’t exist in reality, then how to explain the very real computations?

Daniel Mehkeri

John Templeton Foundation: New Mission Statement May 14, 2010

Posted by Alexandre Borovik in Uncategorized.
add a comment

The John Templeton Foundation serves as a philanthropic catalyst for discoveries relating to the Big Questions of human purpose and ultimate reality. We support research on subjects ranging from complexity, evolution, and infinity to creativity, forgiveness, love, and free will. We encourage civil, informed dialogue among scientists, philosophers, and theologians and between such experts and the public at large, for the purposes of definitional clarity and new insights.

Our vision is derived from the late Sir John Templeton’s optimism about the possibility of acquiring “new spiritual information” and from his commitment to rigorous scientific research and related scholarship. The Foundation’s motto, “How little we know, how eager to learn,” exemplifies our support for open-minded inquiry and our hope for advancing human progress through breakthrough discoveries.

Approximate bases, sunflowers, and nonstandard analysis January 20, 2010

Posted by Alexandre Borovik in Uncategorized.
add a comment

Just a link to Terry Tao.

Ordering the infinite time November 15, 2009

Posted by Alexandre Borovik in Uncategorized.
4 comments

 

Here is an example of a wonderfully consistent theological perspective on time:
In his Systematic Theology, Vol. III, Wolfhart Pannenberg argues that God as eternal comprehends the different moments of time simultaneously and orders them to constitute a whole or totality. The author contends that this approach to time and eternity might solve the logical tension between the classical notion of divine sovereignty and the common sense belief in creaturely spontaneity/human freedom. For, if the existence of the events constituting a temporal sequence is primarily due to the spontaneous decisions of creatures, and if their being ordered into a totality or meaningful whole is primarily due to the superordinate activity of God, then both God and creatures play indispensable but nevertheless distinct roles in the cosmic process.
[J. A. Bracken, A new look at time and eternity, Theology and Science, 2 no. 1 (2004), 77—88. DOI: 10.1080/1474670042000196621.]

 

RAE/REF and the ‘economic and social impact’ of research October 25, 2009

Posted by Alexandre Borovik in Uncategorized.
add a comment

Most likely you have heard about HEFCE’s proposal that in the REF (a  replacement for the RAE) 25% of future research funding would be  allocated according to the ‘economic and social impact’ of submitted  research. Many of our colleagues believe that this ‘impact’ proposal  represents an attack on the knowledge process and constitutes a threat  to the existence of basic research activity in the UK.

What appears to be missing from the increasingly intensive discussion is that the REF proposal provides not just the poison to kill independent  academic research, it offers a syringe for injection, too. The latter is described in a few innocuous lines about the aims of the exercise:

“We will be able to use the REF to encourage desirable behaviours at three levels:

  • THE BEHAVIOUR OF INDIVIDUAL RESEARCHERS WITHIN A SUBMITTED UNIT […]“

[http://www.hefce.ac.uk/pubs/hefce/2009/09_38/09_38.pdf , page 8]

The emphasis on inducing change in the behaviour of “individual researchers” is the result of a slow evolution of the RAE/REF. In 1996 and in 2001, the RAE went to great lengths to ensure that individual researchers could not be identified in the panels’ responses. This changed in 2008, when the percentages of the submission with each number of stars were published. So it was possible, in the case of a small unit, to work out exactly how many papers were internationally excellent, etc., and make a fairly good guess which papers they were.

The passage in the REF proposal concerned with “individual researchers” is much more worrying, especially since this time “the overall excellence profile will combine three sub-profiles – one for each of output quality, impact and environment – which will also be published.”

If “behaviour” just meant “doing good/bad/no research”, it would not be so terrible, but since extraneous things like “impact” now loom large, HoDs will be able to use this to warn staff off doing their preferred research and onto more “impactful” projects. There is a danger that, at department level, the REF might be translated into unheard of levels of bullying and harassment.

Please sign the Number 10 Petition:

http://petitions.number10.gov.uk/REFandimpact/

Please also sign the UCU petition STAND UP FOR RESEARCH (even if you are not an UCU member; signing is open to everyone):

http://www.ucu.org.uk/standupforresearch

Israel Gelfand October 6, 2009

Posted by Alexandre Borovik in Uncategorized.
add a comment

Israel Gelfand (Израиль Моисеевич Гельфанд) passed away yesterday. RIP.

L’infini vu par Noémie July 17, 2009

Posted by Alexandre Borovik in Uncategorized.
7 comments

L’infini
Les galaxies,Les rimes en* I*,
le pipi,Et puis………
Ne fait pas la comédie
Mais c’est joli l’infini…
Et puis c’est pas fini!!
Noémie Kantor
(18 Mai 2000)

From Mathieu Marion July 17, 2009

Posted by Alexandre Borovik in Uncategorized.
4 comments

I do not know if this is of interest to you or not but here is a thought-experiment of mine, probably around the age of 7-8, for sure after 6 and before 10.

I started thinking about death and wanted to convince myself I would never die, instead of thinking about life after death… So I started thinking about an infinity in this way: first, I assumed that my entire life was only one dream in one night in another life where I am still the same person but could not fully realize that a full life goes on in each dream (an interesting point about personal identity, I guess). Now, that other life would be finite and have only a finite number of nights. So, I thought further that in each night there must be a finite number of dreams, encapsulating a finite number of lives. This was still short of infinity, so I started thinking that in each of these finitely many dreams of the finitely many nights, I would live a life that would in turn contain finitely many nights, which would contain finitely many dreams, and so on. I was not so sure that I was safe that way (i.e. that I would go on living forever), but I convinced myself that these were enough lives to live, so that even if the process would end, I would still have lived enough, and stopped thinking about it.

One more image March 31, 2009

Posted by Alexandre Borovik in Uncategorized.
add a comment

c4cimage10