Wikipedia:Reference desk/Archives/Mathematics/2008 November 2

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

November 2

'Mistake' in counterexamples in topology

I was looking at the 'evenly spaced integer topology' (example 58 in the first edition of counterexamples in topology) when I noticed a mistake:

According to the example, the basis sets for a topology on the integers are simply 'cosets of subgroups of the integers'. But this means that the topology is discrete since {0} is a subgroup of the integers, and any coset of it (relative to the integers) is a one-point set.

Another description of the topology given was:

The topology generated by sets of the form a+k*Z = {a + kj | j is in Z} where Z is the set of integers and a and k are fixed and belong to Z. If I put k=0 (which is in Z!), then I obtain the singleton {a} so the topology is generated by one-point sets and must be discrete. However, in 58.4 (property 4 of this example), it is written that one point sets are closed and not open. It is also written that the evenly spaced integer topology is of the first category (false if it is discrete) and that it is not locally compact (false also if it is discrete).

This seems an unlikely error but I am not able to understand why this is not an error. Either I am totally confused or there is a mistake. Could someone please give their opinions on this. Also, this is the first edition so if it is an error, it could have been changed by the second edition (which I don't have access to).

Thanks in advance.

Topology Expert (talk) 05:07, 2 November 2008 (UTC)

I don't know what edition it is, but searching for "evenly spaced integer topology" on Google gives this [1], which specifically excludes that case. It defines the topology as generated by all sets of the form a+kZ, with k not equal to 0. So if your book doesn't exclude that, it's probably an oversight. Black Carrot (talk) 07:35, 2 November 2008 (UTC)

Thankyou black carrot. I think that the book you cited is the second edition because it has a chapter on metrization theory which my book does not. Perhaps, the authors realized this mistake and corrected it in the second edition (I am certain that the first edition does not have the requirement that k is not 0).

Topology Expert (talk) 09:28, 2 November 2008 (UTC)

That's the topology (the later one without the {0})!) used in Hillel Fürstenberg's amazing proof that there's an infinite number of primes and quoted in Proofs from the book. Dmcq (talk) 09:41, 2 November 2008 (UTC)

Wiki contains everything. Furstenberg's proof of the infinitude of primes Dmcq (talk) 09:47, 2 November 2008 (UTC)

Amazing (but simple!)!

Topology Expert (talk) 09:53, 2 November 2008 (UTC)

Prufer code Cryptography?

I was wondering, since graph isomorphism is NP-hard, and Prufer codes show low locality (as described in a reference in the Prufer code section), whether a viable cryptographic encoding would be something like this:

1. Turn the message into a list of n-2 numbers, ranging from 1 to n.
2. Interpret this list as a Prufer code and turn it into a spanning tree.
3. Permute the vertices of the tree using a random permutation (the key).
4. Turn the permuted tree into a list of numbers again.

Decryption would use the same scheme, except with the inverse permutation. Is there something I'm not seeing about spanning trees and graph isomorphisms that would make this not as hard as I'm thinking? --Zemyla^t 06:25, 2 November 2008 (UTC)

"since graph isomorphism is NP-hard" - prove it, collect your turing award. Anyways, that might be a reasonable symmetric block cipher, although surely some block chaining mechanism needs to be added. There is one weakness that I can see: easy instances of the graph problem leak the key, and they might be common.

Suppose for example you have an encrypted disk image. Due to the design of the os all disk images have to start with a zero block and 1, 2, 3, 4, 5, 6 is your integer encoding for zero blocks. The prüfer algorithm will generate the line graph 7-1-2-3-4-5-6-8, the secret permutation swaps the labels, the prüfer algorithm turns it back to a sequence of integers, that gets encoded as bits and then finally written to disk.

The attacker takes hold of the encrypted disk image and reads the ciphered the graph from the first block. Suppose he gets 1-5-4-3-6-7-8-2. Now guess, what was the random permutation? Not really NP-hard. The attacker can trivially narrow the keyspace down to two elements and try both to decrypt the rest of the disk image. —Preceding unsigned comment added by 84.187.75.180 (talk) 08:29, 2 November 2008 (UTC)

It may well work, but unless it works better than other methods, people wouldn't necessarily use it. There are lots of ways of encrypting data. --Tango (talk) 22:03, 2 November 2008 (UTC)

The Toronto Problem

A famous problem in topology which states:

Is every Hausdorff Toronto space discrete? (A space X is called a Toronto space if for every subspace A of X such that card(A) = card(X), A is homeomorphic to X).

Despite extensive research, I have not been able to find out whether this problem has been solved (or not). Does anyone know whether this conjecture has been proven (or disproven)?

Thanks in advance.

Topology Expert (talk) 09:57, 2 November 2008 (UTC)

Largests prime with no holes?

I've read Prime and related articles and I failed to find a statement of the largest prime number for which for every lower number it is known whether they are prime or unprime. It wasn't obviously on http://primes.utm.edu/ either. Anyone know what it is at present - I presume some computer somewhere is slowly churning through them all and the value changes daily. -- SGBailey (talk) 10:25, 2 November 2008 (UTC)

Prime-counting function seems to quote actual counts of primes up to 10²³, would somebody have actually gone ahead and spent electricity on that? Dmcq (talk) 10:35, 2 November 2008 (UTC)

I hadn't read that article. However that doesn't mean that all primes below 10^23 are known - though it seems likely. Equally it doesn't mean that they aren't know up to (eg) 10^30. Teh prime pages do list the first 50 million primes, so that is definitely known. -- SGBailey (talk) 10:52, 2 November 2008 (UTC)

I don't know about primes in general, but the largest known primes are Mersenne primes and for those they know there are no holes up to the 39th, but no higher (there are 46 known). There are most likely non-Merseene primes inbetween them, of course. --Tango (talk) 13:18, 2 November 2008 (UTC)

There are certainly non-Mersenne primes between any two Mersenne primes, by Bertrand's postulate for example. Algebraist 16:50, 2 November 2008 (UTC)

So back to the original question. Anyone know what is the current largets prime for which ALL lower primes are also known? A reference with any value would be nice. -- SGBailey (talk) 21:04, 2 November 2008 (UTC)

PrimeHunter will know, if no-one else does. Algebraist 21:11, 2 November 2008 (UTC)

This question might be rather subtle. Suppose I claim that 41938296735073811 is the largest prime for which all lower primes are also known. (Never mind the fact that 41938296735073811 might not be prime; I just typed some digits.) How would I justify my claim? By the prime number theorem, there are about $10^{15}$ prime numbers less than 41938296735073811. Would I have to have a database somewhere listing all $10^{15}$ of these primes, with proofs of their primality, and also listing all of the remaining $4\times 10^{16}$ composite numbers, with proofs of their non-primality? —Bkell (talk) 02:37, 3 November 2008 (UTC)

The question, I suppose, is what you mean by "known". I would say that the answer to the addition problem 3147318947318973429933+8472336130058463383 is "known", because if I want to know the answer I can easily figure it out. In this sense the answer is "known" even though probably no one has ever before actually worked out this particular addition problem. Undoubtedly the prime P you refer to is of only a "few" digits (40 or 50 digits at most), and verifying the primality or non-primality of such a number doesn't take very long on modern computers, I think. So, given an arbitrary integer N less than P, what difference does it make whether someone has previously asked a computer whether N is prime or not? If you want to know, you can just find out for yourself with no trouble. If what you're really interested in is how many prime numbers there are less than P, then what you want to look at are the methods for computing the prime-counting function. —Bkell (talk) 02:52, 3 November 2008 (UTC)

PrimeHunter is here! My watchlist showed an edit summary with the section name which caught my interest. I was amused to see that Algebraist has referred to me. See http://primes.utm.edu/notes/faq/LongestList.html. After my post at [2] it added mention of what is, as far as I know, the largest number of computed primes: Tomás Oliveira e Silva's Goldbach conjecture verification project at [3]. It uses the ancient Sieve of Eratosthenes and currently says: "July 14, 2008: 12·10^17 reached". This means the project has computed all 29554545057338187 primes below 12·10^17. But each prime was only kept briefly in ram on one of the computers participating in the distributed project. Storing so many primes is not really an option. An ordinary PC can compute many billions of primes per hour. However, the claim at http://primes.utm.edu/notes/faq/LongestList.html of less than a minute for primes below 1,000,000,000,000 is not true. Maybe the author intended to write something else. It's said that efficient programs can compute primes faster than they can be read from a harddisk (and much faster than most Internet connections), so there is little point in creating huge databases of primes. The largest database I have seen (without wasting time trying to download it) is by PrimeGrid at [4]. It says it has all primes below 210000000000 which means 8391034591 primes. That requires many gigabytes but could easily be computed in less than an hour on a PC (although PrimeGrid actually used a very slow program for it). It would be possible to set up a site which claimed to have a prime database but really computed primes on the fly faster than they are downloaded. Of historical interest, http://www.1911encyclopedia.org/Mathematical_Table mentions some old printed tables from before computers.

Known formulas for the prime-counting function can compute the number of primes below a given limit much faster than the actual primes can be computed. The published prime counts above 12·10^17 (the current record is 10^23 by Tomás Oliveira e Silva at [5]) were made without computing the primes. I guess the smallest prime which has never been computed is a little above 12·10^17. But if a possible value was published then the next many primes could be computed in a fraction of a second.

By the way, my first guess was that the section heading "Largests prime with no holes" referred to the largest known prime with no digit containing a "hole" (as in 0, 6, 8, 9 and maybe 4). Such primes have actually been studied and named. http://primes.utm.edu/lists/top_ten/topten.pdf (which is not maintained and contains obsolete records) has a record table "The TOP TEN Unholey Primes". The current record may be in [6] which is about a 82000-digit prime only containing the prime digits 2, 3, 5, 7. If probable primes are allowed then I guess the record is the largest known probable repunit prime in [7] with 270343 digits - all of them 1's. PrimeHunter (talk) 04:28, 3 November 2008 (UTC)

Spider solitaire

What is the highest possible attainable score? --Shaggorama (talk) 18:10, 2 November 2008 (UTC)

According to Spider (solitaire), several scoring systems exist. Which do you have in mind? Algebraist 19:12, 2 November 2008 (UTC)

windows scoring --Shaggorama (talk) 06:33, 6 November 2008 (UTC)

Equivalence of 0-1 matrices

If I have two 0-1 matrices (all entries are either 0 or 1), both of the same size (and in fact square), is there a fast way to tell whether one can be produced from the other by a sequence of row swaps and column swaps? My initial idea is to do row swaps to put the rows in order by the number of 1's they contain, then do the same for the columns, to get a "canonical" form for the matrix, and then see if the canonical forms of the matrices are the same. But this isn't going to be enough. For example:

$A={\begin{bmatrix}0&1&1&1\\0&1&0&1\\1&0&0&1\\1&0&0&0\\\end{bmatrix}}$, $B={\begin{bmatrix}0&1&1&1\\1&0&0&1\\0&1&0&1\\1&0&0&0\\\end{bmatrix}}$.

Clearly B is formed from A by swapping the second and third rows. But my proposed sorting procedure, assuming a stable sort, gives

$A_{\mathrm {sort} }={\begin{bmatrix}0&1&0&0\\0&0&1&1\\0&1&0&1\\1&0&1&1\\\end{bmatrix}}$, $B_{\mathrm {sort} }={\begin{bmatrix}0&1&0&0\\0&1&0&1\\0&0&1&1\\1&0&1&1\\\end{bmatrix}}$.

This seems to be something I should know from linear algebra, but my linear algebra knowledge is pretty spotty. —Bkell (talk) 21:01, 2 November 2008 (UTC)

I think you want Row echelon form (in particular, the reduced row echelon form). --Tango (talk) 21:20, 2 November 2008 (UTC)

But the echelon forms allow adding one row to another, not just swapping rows. Swapping rows and columns corresponds to permuting the elements of the given bases, rather than to an arbitrary change of basis. Algebraist 21:24, 2 November 2008 (UTC)

Sorry, yes. I didn't read the question carefully enough - I saw "equivalence" in the title and assumed it was about the standard definition of equivalent matrices. --Tango (talk) 21:32, 2 November 2008 (UTC)

Ok, take two: How about sorting the columns by number of 1's, then sorting the rows by lexicographic ordering? That seems to work for your example. You may have problems with ties, I'm not sure. --Tango (talk) 21:36, 2 November 2008 (UTC)

Yes, you will still have problems with ties in the first sort (it's easy to find an example)... I don't think using lexicographic ordering for both sorts will work, though... I'm still thinking. --Tango (talk) 21:40, 2 November 2008 (UTC)

I had considered doing my sorts based on the number of 1's, and breaking ties using lexicographic ordering, but if you do this to the rows and then the columns, you might put the rows out of order lexicographically. So, I thought, maybe you just re-sort the rows, and then re-sort the columns, and keep doing this until nothing changes, but I'm not convinced that you won't find yourself in a never-ending loop. —Bkell (talk) 21:51, 2 November 2008 (UTC)

The open source GAP computer algebra system command for this is TransformingPermutations. It first sorts rows, and then executes a permutation group backtrack search on the columns inside a group that stabilizes a few invariants of the matrix. It is intended to be used on arbitrary pairs of matrices, so some of the invariants are not likely to be useful for 0-1 matrices, but the general idea should be useful. 74.140.212.193 (talk) 00:45, 3 November 2008 (UTC)

After some reflection, I realize that this is probably not a trivial problem, because it is at least as hard as the graph isomorphism problem, which is not known to be solvable in polynomial time. Thanks for the idea, 74; I'll try to come up with something along those lines. —Bkell (talk) 02:18, 3 November 2008 (UTC)

In fact it is precisely equivalent to the graph isomorphism problem and not easier or harder either in theory or in practice. To get from a graph to a matrix, use one row per vertex and one column per edge, then put a 1 when the vertex is on the edge. To get from a matrix to a graph, make one black vertex for each row and one white vertex for each column, then join them where there is a 1. McKay (talk) 02:32, 3 November 2008 (UTC)

Ah, yes, you're right. My comment above was based on the observation that not all square 0-1 matrices are adjacency matrices, but of course they are all adjacency matrices for bipartite graphs in the way you describe. —Bkell (talk) 02:55, 3 November 2008 (UTC)