Wikipedia:Reference desk/Archives/Mathematics/2010 October 23

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.

October 23

the four-color theorem doesn't seem right to me

I can always come very close to producing a counter-example. What is the probability that the four-color theorem really is wrong, as it seems to me? If there is a simple, intuitive proof, maybe you could tell me it? 84.153.222.131 (talk) 15:40, 23 October 2010 (UTC)

Have your read our Four color theorem article? Basically, there is no known proof that is small enough to be checked by hand, but several independent computer-assisted proofs and at least one computer-verified formal proof have been constructed, and it is pretty implausible that they are all flawed.

I cannot imagine any meaningful sense in which one could assign a definite "probability" (other than 0 or 1) to the theorem being untrue. –Henning Makholm (talk) 16:00, 23 October 2010 (UTC)

See Bayesian inference for a paradigm in which assigning such probabilities makes sense. Robinh (talk) 16:10, 23 October 2010 (UTC)

I said "I cannot imagine any meaningful sense in which...". Pulling numbers out of one's ass and pretending that they have anything to do with the subject under discussion does not count. –Henning Makholm (talk) 16:53, 23 October 2010 (UTC)

Bayesian probability doesn't pretend to describe the subject under discussion, but rather our state of knowledge about the subject under discussion. This is of crucial importance in epistemology and decision theory. An example for someone making a decision based on his credence for the correctness of a proof is this. -- Meni Rosenfeld (talk) 07:29, 24 October 2010 (UTC)

I thought one pulled a prior out of thin air, not a posterior out of one's ass. Robinh (talk) 18:42, 24 October 2010 (UTC)

There is a relatively simple proof of the weaker Five color theorem. It does take several big steps to fully understand, though. If you want to give it a shot, here's a list of things you can look at:

1. Understand the translation of the map coloring problem into that of coloring graphs. This is explained in this section of the Four color theorem article. If you aren't already familiar with graph theory, you might want to play with those a little; a famous theorem that might help you get acquainted with graphs is the condition under which an Eulerian path exists (though that is not crucial to understanding the proof of the five color theorem).
2. Study the Euler characteristic for planar graphs. If a graph is planar, then we can count not only edges and vertices, but regions enclosed by the edges as well. It turns out that these three quantities satisfy a nice rule, V-E+F=2. The proof of this fact is outlined in that article.
3. Figure out why the Euler characteristic implies E ≤ 3V − 6 (assuming the planar graph has at least 3 edges). This can be algebraically derived from knowing that every edge touches at most two regions and every region touches at least 3 edges.
4. From this fact, prove that every planar graph must have some vertex of degree 5 or less.
5. If you are sufficiently well versed in proof by induction, a proof that every planar graph can be colored with 6 colors should follow naturally, knowing that last fact. Turning this into a proof that every planar graph can be colored with 5 colors requires a clever trick, which is explained in the article on the five color theorem. Why can't the same trick be used to prove the Four color theorem?

HTH. --COVIZAPIBETEFOKY (talk) 16:29, 23 October 2010 (UTC)

Actually, I have a vague memory of having heard an argument quantifying the sentiments of the IP supra. The argument, as far as I remember, went like this:

A graph is 4-colourable, iff 4 is a zero for its chromatic polynomial. Thus, the 4CT is equivalent to proving that the cromatic polynomial of any planar graph has a value strictly greater than zero at 4. However (the argument went), it is possible to prove (don't ask me how!) that there are zeros arbitrarily close to 4 for the set of all chromatic polynomials for planar graphs. One conclusion was very similar to the IP's: The 4CT is "almost false".

Thus, if you have found a reasonably "natural" family of "almost counterexamples", it might be interesting to check whether or not the set of zeroes of the chromatic polynomials of the graphs in this family has 4 as a limit point.

I'm sorry for not remembering more details. Possibly, some reference at or close to Chromatic polynomial#Chromatic roots might help. JoergenB (talk) 18:32, 29 October 2010 (UTC)

Help me impress my friend?

Hey I'm trying to pretend I know something about calculus to impress my friend. Technically that's why I want the answer to this question, it's not (my) homework.

So..

1/⅔ × sqrt(X) × constant = 3/2 X

What is the value of constant?? It's from a first year calculus course, I've already taken it, but I don't know where to start on this question. —Preceding unsigned comment added by 174.89.36.96 (talk) 16:07, 23 October 2010 (UTC)

This is not calculus. It is algebra. You need to isolate the X on the right. Multiply both sides by 2/3 and you'll have a very simple formula. However, the "constant" is not a constant. -- kainaw™ 16:28, 23 October 2010 (UTC)

(e/c) This isn't calculus, it's algebra. There is no differentiation or integration involved. Looking at your problem you have

${\frac {1}{2/3}}\times {\sqrt {x}}\times k={\frac {1}{2}}(3k{\sqrt {x}}).$

You claim that this is equal to 3x/2, i.e.

${\frac {1}{2}}(3k{\sqrt {x}})={\frac {3}{2}}x\iff k{\sqrt {x}}=x\iff k={\sqrt {x}}.$

But this doesn't really make sense. You see, x is usally though of as a variable. That means you would solve the equation for x and not k. (k was a constant after all, and was fixed.) A more likely solution would be

${\frac {1}{2}}(3k{\sqrt {x}})={\frac {3}{2}}x\iff x=0,k^{2}\ .$

If there's something you forget to mention then let us know. It will change the problem and hence change the answer. — Fly by Night (talk) 16:30, 23 October 2010 (UTC)

Ok thanks a lot guys, I asked if there are more details, but that seems to be the whole question. For now I guess this is resolved, I was hoping I was missing some advanced calculus technique that would let me find a genuine constant.

Hopefully she's impressed —Preceding unsigned comment added by 69.165.137.230 (talk) 17:08, 23 October 2010 (UTC)

If she knows calculus, she will quickly spot your naive error: your assumption that "any complicated math is calculus." Once you are outed thusly, she will see through your charade and will probably be unimpressed by you (and will likely consider your stunt a poor indicator of character). To avoid this eventuality, you should educate yourself first by reading our articles on algebra and calculus, (and your textbooks) and work out as many practice problems as you can. Girls (or guys) who would be impressed by pseudo-calculus are of dubious quality. You should stick to actually knowing things; this will impress everybody, including those girls who actually know calculus. Nimur (talk) 18:03, 23 October 2010 (UTC)

Quite the opposite! If she knows calculus, and realizes he's only pretending to, she is far more likely to find him a hot boy-toy, ie physically lust for him, than otherwise. In fact, if he were a Fields-metal level genius, it would only hurt his chances... 84.153.221.42 (talk) 18:44, 23 October 2010 (UTC)

I beg to differ! Nimur (talk) 18:46, 23 October 2010 (UTC)

Sir, may I ask you, kindly to leave the inquiring gentleman's delusions intact? If indeed his friend can tell calculus from pseudocalculus, it would be discourteous to deny her this opportunity to form an accurate assessment of his moral character. –Henning Makholm (talk) 18:55, 23 October 2010 (UTC)

The idea that one might be able to use pseudo-calculus as an effective dating tool implies such a fundamental misunderstanding of dating interactions and the psychology of women that I don't see any real possibility that anything we say will un-delude this guy. Just give him a Darwin Award for trying, because if he keeps it up it's extremely unlikely he will ever reproduce. --Ludwigs2 19:06, 23 October 2010 (UTC)

Unless he becomes a sexual predator. 67.243.7.240 (talk) 23:53, 24 October 2010 (UTC)

Don't worry she doesn't know too much calculus. —Preceding unsigned comment added by 99.224.233.138 (talk) 19:21, 23 October 2010 (UTC)

See [1] for a joke about assuming a waitress doesn't know calculus. I think the whole business is a bad idea. Dmcq (talk) 22:07, 23 October 2010 (UTC)

secure hash

how to securely hash any two numbers each over 100 digits long into a number between 1 - 10 with equal distribution/probability. The easier the hash is to explain/follow, the better. this is not homework. thank you! 84.153.221.42 (talk) 18:41, 23 October 2010 (UTC)

How about modulo ten? There is no way to avoid hash collision with your scenario, so why try? Nimur (talk) 18:44, 23 October 2010 (UTC)

What do you mean? How do you combine the numbers? Anyway both my numbers are odd (they're large primes), so if you're adding them, you would only ever get 2,4,6,8, or 0 and never any of the other numbers. Do you have a better suggestion, that would use more of the digits of both numbers? (and 'depend' on both of them) 84.153.221.42 (talk) 18:55, 23 October 2010 (UTC)

(ec) Just add all the digits modulo ten. If you want something "more secure", you'll need to specify which kind of security property you're thinking about (since quite clearly the usual characteristics of a cryptographic hash functions are unachievable with an output that small). –Henning Makholm (talk) 19:02, 23 October 2010 (UTC)

(Is what you're looking for perhaps not a hash but a message authentication code? –Henning Makholm (talk) 19:05, 23 October 2010 (UTC)

Yes, I am looking for a message authentication code, but that article says it is sometimes called a keyed (cryptographic) hash function. This is the sense in which I used the word "hash". 84.153.221.42 (talk) 20:08, 23 October 2010 (UTC)

From a security standpoint, the recommendation would be something tried and true, such as HMAC-SHA1, and then use mod 10 (or whatever) to cut `it down to the size you want. If you insist on simpler calculations (always at the risk of accidentally introducing cryptographic weaknesses), you'll need to be much more explicit about which threats you want to secure against. –Henning Makholm (talk) 20:28, 23 October 2010 (UTC)

Well, I don't really want to secure against anything so much as make sure that there is an equal distribution.... 84.153.221.42 (talk) 20:38, 23 October 2010 (UTC)

To be clear, you want a hash function mapping into {1, ..., 10} which has a roughly uniform distribution for input primes in the ~100's of digits? How about... just take the first two (i.e. most significant) nonzero decimal digits mod 10? I'd be surprised if the distribution was much different from uniform. Of course you should try it out with a thousand or so test cases to see. (I'm guessing you just want something decent, not perfect, and an attacker isn't in the picture. If these assumptions are incorrect, please clarify the question.) 67.158.43.41 (talk) 04:44, 24 October 2010 (UTC)

I'm not sure what you mean by "securely" here. It's not possible to achieve any of the usual security properties of a cryptographic hash function if the function can only take 10 distinct values; in particular, even if the hash was a random oracle, it would only take on average 10 queries to find a preimage for any output. —Ilmari Karonen (talk) 19:01, 23 October 2010 (UTC)

By the way, is modulo 10 equally distributed?

rand() % x in c is not equally distributed, as it slightly favors smaller numbers over larger ones. Would it be equally distributed 1-10 when applied to the sum of the digits of two primes? 84.153.221.42 (talk) 20:09, 23 October 2010 (UTC)

This isn't answering your question, but a more important reason that rand()%x might not be uniformly distributed in C is that the pseudorandom number generator used in many C libraries does not produce uniformly distributed least-significant bits. —Bkell (talk) 06:18, 24 October 2010 (UTC)

also followup

is your recommendation the same if we need a number 1-10, 1-100, 1-500. 1-1000, or 1-5000? (assuming we're looking at primes several hundred digits long.) 84.153.221.42 (talk) 20:11, 23 October 2010 (UTC)

terminology

Resolved

add two things. The resulting sum...
multiply two things. The resulting product...
take modulo 5. The resulting _____?

what is the missing word? 84.153.221.42 (talk) 20:36, 23 October 2010 (UTC)

Remainder or residue. –Henning Makholm (talk) 20:42, 23 October 2010 (UTC)

Thanks!

can you find an n-digit prime?

I know for binary digits, you can -- encryption uses, for example, 512-bit primes. Can I ask you to find an exactly 100-digit prime (or 500, etc), expressed in decimal? 84.153.221.42 (talk) 22:20, 23 October 2010 (UTC)

Yes, you can ask. Whether anyone will bother to actually do it for you is another matter. If you google for prime number generator, you will find websites and free software that purport to do things like this for you. –Henning Makholm (talk) 22:32, 23 October 2010 (UTC)

There always exist primes with any desired number of digits. The known bounds on the prime-counting function imply that for any $n>e^{\ln 2+10}\approx 44053$ there is at least one prime between n and 2n, and this property also holds for smaller n (by inspection of tables of primes). –Henning Makholm (talk) 23:06, 23 October 2010 (UTC)

Also see Bertrand's postulate. --Sam^Talk 05:15, 24 October 2010 (UTC)

Ah, that's slicker than the pedestrian argument I used. Thanks. –Henning Makholm (talk) 13:24, 24 October 2010 (UTC)

The following 500 decimal digits number is almost certainly a prime:

9871615190774109714631411860249057511981491262347298846971208567428248575453148043285875030217607786541394670874
1765030099536818318173353655505066711178433481944388749902895601864112760848063528268606416757060899302271352925
5864263819518034812848659084214983995663078865233769085509471793209927625145995901711340039317987632029515022435
2487509247090084455951957030991069493698109678946205440148128949032618192971706584082407007804900529851119894058
1723948298045506883722180286057686368471530972548567

-- Meni Rosenfeld (talk) 07:04, 24 October 2010 (UTC)

Encryption software just tests randomly chosen numbers of the appropriate size for primality, and that can just as well be done with decimal digits. But even not knowing that, it follows from the fact that you can find primes for any number of binary digits that you can find them for any number of decimal digits. For example, 2³²⁹ through 2³³² all have 100 decimal digits, so if you can find a prime of 329 to 331 binary digits then you've found a prime of 100 decimal digits. -- BenRG (talk) 07:13, 24 October 2010 (UTC)