Linear Sudoku
Number theory remains a playground for amateurs, despite applications continuing to unfold in crystallography, cryptography, signal processing, etc. But the playground has gone hi-tech in recent years, as sheer number-crunching power has overcome many limitations on just how far computation can take you. (At most, I myself am an applied mathematician; that is, I’m not really a mathematician, but I play one on PC.)
The use of computers in formal proofs is controversial. The first incursion on the hallowed grounds was the 4-color theorem; more recently, sphere-packing (Kepler’s conjecture) succumbed to cannonballs of brute force aimed expertly at the ramparts. The common theme is that all contingencies are partitioned out in a solution space that, while beyond the capacity of human calculation, the computer can properly traverse. Hales insists this is merely groundwork for an acceptable higher order proof, and similar efforts to clean up 4CT persist
Computers are better accepted as a research tool in extending the horizons of number theory – not so much for formal proof as for buttressing conjectures, or finding counterexamples, in exploring a limitless search space, the integers. This is done via voluntary distributed processing: The best-known effort is the search for large prime numbers, while a similar less heralded effort goes on to determine optimal Golomb rulers. On which, more, directly.
A close analogue is the way computers play chess. Early attempts to replicate human modes of analysis were (and still are) an abject failure. The way forward was to make the best use of what computers do best, iteration and computation. (And a third component, memory, as applied to opening play and checking endgames against known results.) Iteration involved building a tree of all possible moves from a given position, defining a search space, but the combinatorial explosion in potential moves limits how far out this can go. The computational aspect is in evaluating the resulting positions in terms of balance (not just material, but control of space and other tactical and positional factors) and stability (to determine whether to evaluate positions further down the tree; for a simple instance, if there are checks available to either side). Optimizing the interaction between iteration and computation is what lends strength to the result; it also governs strategies for human play against computers, in which long-term strategic considerations, beyond the horizon that such iterated computation can detect, become the tactic. And now top-tier grandmasters even participate in match-play tournaments that incorporate computer assistance (‘Advanced Chess’).
Back to Golomb rulers: These first came to my attention via Kevin S. Brown’s Math Pages (though in an earlier [seanet] version than this one). In short, Golomb rulers are a linear set of points in the integers with distinct pairwise distances. The aspect I found most interesting was that of isospectral (or homometric) rulers. Before Golomb came along, one of the few recognized woman in mathematics of her day, Sophie Piccard, a good mathematician, made a bad guess in 1939, towhit: That if X and Y are two Golomb rulers with N points with the same set of point-to-point distances, then X=Y (up to rotation). The counterexample was discovered by G.S.Bloom in 1975:
0 1 . . 4 . . . . . 10 12 . . . . 17
|-|- - -|- - - - - -|- -|- - - - -|
0 1 . . . . . . 8 . . 11 13 . . . 17
|-|- - - - - - -|- - -|- -|- - - -|
The conjecture was modified to exclude N=6. I don’t think this goes deep enough; it’s a kludge where a hack can do service. I think that this is another example of how perfect numbers operate (not ‘perfect rulers’, which include all integer distances, e.g. {0 1 3}) (and related, by the by, to the Mersenne primes), and that the proper statement of the conjecture is: If X and Y are two Golomb rulers with N points with the same set of point-to-point distances, and X≠Y, then N is perfect. (I also suspect that these will exist amongst the optimal N-point rulers.) When the Distributed OGR project gets up to 28 (now grinding away at 25), we’ll see whether this pans out. Unless someone finds a short-cut …
The use of computers in formal proofs is controversial. The first incursion on the hallowed grounds was the 4-color theorem; more recently, sphere-packing (Kepler’s conjecture) succumbed to cannonballs of brute force aimed expertly at the ramparts. The common theme is that all contingencies are partitioned out in a solution space that, while beyond the capacity of human calculation, the computer can properly traverse. Hales insists this is merely groundwork for an acceptable higher order proof, and similar efforts to clean up 4CT persist
Computers are better accepted as a research tool in extending the horizons of number theory – not so much for formal proof as for buttressing conjectures, or finding counterexamples, in exploring a limitless search space, the integers. This is done via voluntary distributed processing: The best-known effort is the search for large prime numbers, while a similar less heralded effort goes on to determine optimal Golomb rulers. On which, more, directly.
A close analogue is the way computers play chess. Early attempts to replicate human modes of analysis were (and still are) an abject failure. The way forward was to make the best use of what computers do best, iteration and computation. (And a third component, memory, as applied to opening play and checking endgames against known results.) Iteration involved building a tree of all possible moves from a given position, defining a search space, but the combinatorial explosion in potential moves limits how far out this can go. The computational aspect is in evaluating the resulting positions in terms of balance (not just material, but control of space and other tactical and positional factors) and stability (to determine whether to evaluate positions further down the tree; for a simple instance, if there are checks available to either side). Optimizing the interaction between iteration and computation is what lends strength to the result; it also governs strategies for human play against computers, in which long-term strategic considerations, beyond the horizon that such iterated computation can detect, become the tactic. And now top-tier grandmasters even participate in match-play tournaments that incorporate computer assistance (‘Advanced Chess’).
Back to Golomb rulers: These first came to my attention via Kevin S. Brown’s Math Pages (though in an earlier [seanet] version than this one). In short, Golomb rulers are a linear set of points in the integers with distinct pairwise distances. The aspect I found most interesting was that of isospectral (or homometric) rulers. Before Golomb came along, one of the few recognized woman in mathematics of her day, Sophie Piccard, a good mathematician, made a bad guess in 1939, towhit: That if X and Y are two Golomb rulers with N points with the same set of point-to-point distances, then X=Y (up to rotation). The counterexample was discovered by G.S.Bloom in 1975:
0 1 . . 4 . . . . . 10 12 . . . . 17
|-|- - -|- - - - - -|- -|- - - - -|
0 1 . . . . . . 8 . . 11 13 . . . 17
|-|- - - - - - -|- - -|- -|- - - -|
The conjecture was modified to exclude N=6. I don’t think this goes deep enough; it’s a kludge where a hack can do service. I think that this is another example of how perfect numbers operate (not ‘perfect rulers’, which include all integer distances, e.g. {0 1 3}) (and related, by the by, to the Mersenne primes), and that the proper statement of the conjecture is: If X and Y are two Golomb rulers with N points with the same set of point-to-point distances, and X≠Y, then N is perfect. (I also suspect that these will exist amongst the optimal N-point rulers.) When the Distributed OGR project gets up to 28 (now grinding away at 25), we’ll see whether this pans out. Unless someone finds a short-cut …
posted by nnyhav | 20:03
0 Comments:
<< Home