manifold-13

[manifold home page] [manifold-13 contents] [next article in manifold-13] [SIGNs in manifold-14]
These navigation links are repeated for convenience at the end of the article.

As the article appeared

signs

Various cautionary tales have been told about the dangers of putting badly-posed problems on a computer. This one illustrates the danger of putting a well-posed but badly understood problem on a computer.

A certain research institute in the States (where else?) had built an exceedingly large, fast computer; and was seeking a suitable problem for the beast to cut its teeth on. An appeal to universities and business firms throughout the country finally produced such a problem, which was the inversion of a certain numerical 500 x 500 matrix. The top left hand corner of this matrix, shall we say, looked like:

 	 5   7  -2 ...
 	 1   4  19 ...
	-6   0  33 ...

	 .   .   . ...

Now it is not an easy tank to invert a large matrix, because the simplest techniques build up rounding errors which may nullify the whole result. So the research institute spent about six months programming the computer. When they finally ran the program, the machine churned out the answer whose top left-hand corner read:

 	 5 7 -2 ... 
	 1 4 19 ... 
	-6 0 33 ...
 	  . . . ...

Whereupon somebody was sent round to the firm which had asked for the matrix to be inverted, with the query 'Where did you get this matrix?' Within five minutes of being told, he produced a proof that the matrix was orthogonal.


In the hierarchy of mathematical honour &c., having one's name attached to an object (Taylor series, Cauchy's theorem) come's fairly low on the list. The next stage is having one's name used adjectivally (Gaussian measure, Archimedean valuation). The first step of any real distinction in when the initial letter in used in lower case (abelian group, euclidean space; Riemann is at present hovering between Riemannian and riemannian manifolds). The highest distinction, however, goes to the man whose name in used an a verb. The only cases we have yet come across are Abel (to abelianize a group) and Markov (to Markovise a stochastic process), and here Abel takes the prize because of his small letter. Honours for the unusual must surely go to Lipschitz, whose name recently appeared an part of the noun lipeomorphism - a map between manifolds satisfying a Lipschitz condition. In this connection the verb 'to degauss' bears consideration.


The Dimension Subgroup Problem, unsolved for thirty years, concerns relations between the lower central series of a group and powers of the augmentation ideal in the group ring. A counterexample has been announced by Rips, of the Hebrew University. The group has order 2 and is nilpoterit of class 3.


These six polygonal tiles

can be used to completely tile the plane. However, as is shown by R.M.Robinson (Undecidability and nonperiodicity for tilings of the plane, Inventiones Math. 12, 1971, 177-209) there is no periodic tiling using them; that is, no tiling in which a finite pattern of tiles in repeated regularly over the whole plane. Until quite recently no such sets of tiles (which cover, but only non-periodically) were known; the above set is the smallest known to date.


In an article in MANIFOLD-12 (Beyond the bound), Michael Forrester raised some doubts about large numbers. Briefly, his article argued that our intuition, at least in respect of arithmetic, is based on notions to do with small finite sets (of apples wives, arrows etc.) and that we could at least be constructively distrustful over numbers like A+1 where we cannot exhibit a set with cardinality A, let alone find the extra 1. (There is an article on the constructivist view on infinity elsewhere in this issue.)

Alan Matheson Turing - known best in connection with Turing machines and work in the theory of computation (The Imitation Game - in MANIFOLD-6) - had similar ideas. These he expressed by claiming that after a certain point numbers become so large as to be (literally) incomparable. More specifically, he produced a function that grew so rapidly that for relatively small values of its arguments it was too large to be compared with other large numbers. One might imagine a competition in which the winner was the person who managed to describe the largest possible number on a standard postcard. Straight decimal notation, though doubtless yielding a massive number, would lose out to repeated factorials and exponentials.

A very real problem would arise in dealing with Turing's apparently innocuous function:

	  F1(X) = 2X + 1 
  	Fn+l(X) = Fn(Fn(Fn ... (X) ... ))

where the composition is taken Fn(x) times.

For x=2, F1 = 5 1 F2 = 95 and F3 is beyond pencil-and-paper calculation. It would be practically impossible to compare something 'simple' like F8 (9) with other concise notations such as 10^10! or 10!!!!!!!!!


The map below represents the two possible routes to South Africa for Concorde; depending upon whether or not it is banned over land because of the sonic boom. We are reminded of the episode in the Goon Show in which the Africa Aeroplane Canal was built so that aircraft wouldn't need to fly round the Cape. And ying-tong-iddle-i-po to you too Neddy!


'Suppose we loosely define a religion as any discipline whose foundations rest on an element of faith, irrespective of any element of reason which may be present. Quantum mechanical for example, would be a religion under this definition. But mathematics would hold the unique position of being the only branch of theology possessing a rigorous demonstration of the fact that it should be so classified.'

F. De Sua.


Richard Brauer, the world's most eminent group theorist, visited Warwick University recently. On his first day here, he said 'There are a lot of group theorists in England.' On his second day, he said: 'There are too many group theorists in England.'


THE FOUR COLOUR PROBLEM

Four colouring a map I can do,
With black and yellow, white and blue,
Five was proved by this fellow
So I take some blue and yellow.
Which mixed produce a greeny hue.

A.K.Austin.


There in a story about a chess player who, whilst passing a cafe, saw two people playing chess through the window, Though he only saw them for a couple of seconds, he pronounced that they were good chess players, by the way they were studying the board. The importance of perception in chess is discussed in the article on computer chess. After good early progress in programming computers to play chess, there has been little Improvement,

Which reminds us of an old Indian proverb: 'Chess is a sea in which a gnat may drink and an elephant may bathe.'



This section is a sequel to our series on Mathematics of the Seventies; we hope to publish further articles in this series in subsequent issues. In particular we hope to publish several articles on catastrophe theory in the next issue of MANIFOLD, including an article by the man who originally invented the subject, Professor ReneThom.

HILBERT'S TENTH PROBLEM (MANIFOLD-8)
Martin Davis has now found another proof that there does not, in general, exist an algorithm to decide whether a given diophantine polynomial equation has solutions (An explicit definition of the exponential function: Comm. Pure Appl. Maths. 24 - 1971, 137-1450) by finding a polynomial P(a, b, u, X1, ... , Xn) such that P=0 has a sol. ution In positive Xi if and only if a=b^u. The work of Dayis, Putnam and Robinson can then be used to complete the proof (see elsewhere in this issue). His P has degree 10 and involves 24 variables; the proof that it has the desired property rests upon the use of the 'Pell' equation. with d+1 a square:
x^2 - dy^2 = 1
Matijasevic, meanwhile, has improved his results about diophantine representation of the set of primes. He can find a polynomial Q(X1, ... Xn) such that p is prime if and only if Q takes value p for some set of i integer Xi's. This Q involves 21 variables and has degree 21. (Sov. Mathematics Dokl.12, 249 -).

INFINITE LINEAR GROUPS (MANIFOLD-9)
The problem about free subgroups of linear groups has now been solved by J.Tits (Free subgroups in linear groups; J.Alg. 20, 1972 250-270). He proves that over fields of characteristic 0 every linear group that in not soluble-by-finite has a non-abelian free subgroup. For fields of characteristic p>O, it is necessary to assume that the group in not soluble-by-(locally finite).

The proof involves techniques of algebraic group theory, and proceeds by reducing the problem to the case of locally compact fields.


COMBINATORIAL GROUP THEORY (MANIFOLD-11) J.L.Britton's proof that the Burnside group B(d, e) is infinite for d>1 and large odd e should soon appear in print. Novikov and Adyan's proof of this, for odd e>4380, occupies some 350 pages. Britton's proof is of comparable length; in principle it too gives a lower bound for e, but its author "has no reason to believe that this bound is better than Novikov-Adyan's ...". It should be stressed that Britton's work is completely Independent of the Russians'. It depends on a generalization of Tartakovskii's investigations into the word problem for groups, and makes use of the Morse-Hedlund sequence abcabc which does not contain a repeated sequence XX. The oddness of e is essential to the proof, but only for technical reasons. Britton has no conjecture to make about even e, except that the best bet for finite groups will be e= a power of 2; in particular he suggests looking at B(2, 8).


[manifold home page] [manifold-13 contents] [next article in manifold-13] [SIGNs in manifold-14]