[math-fun] Existence from parity
What are people’s favorite examples of existence proofs that show that a set is not empty by showing that its cardinality is odd? Jim Propp
Maybe this is not quite what you want - but Another Hamiltoniain Path says that if there is a Hamiltonian path in G, then there is another one either in G or its complement \bar{G}. The idea is to define an (exponentially large) graph in which Hamiltonian paths correspond to the number of odd-degree vertices. There are an even number of these. So… this is sorta an example of odd parity, but it’s really showing that the set plus one has even parity :-) Cris
On Jan 29, 2020, at 7:44 AM, James Propp <jamespropp@gmail.com> wrote:
What are people’s favorite examples of existence proofs that show that a set is not empty by showing that its cardinality is odd?
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Sounds interesting. Do you have a reference? Jim On Wed, Jan 29, 2020 at 11:21 AM Cris Moore via math-fun < math-fun@mailman.xmission.com> wrote:
Maybe this is not quite what you want - but Another Hamiltoniain Path says that if there is a Hamiltonian path in G, then there is another one either in G or its complement \bar{G}.
The idea is to define an (exponentially large) graph in which Hamiltonian paths correspond to the number of odd-degree vertices. There are an even number of these.
So… this is sorta an example of odd parity, but it’s really showing that the set plus one has even parity :-)
Cris
On Jan 29, 2020, at 7:44 AM, James Propp <jamespropp@gmail.com> wrote:
What are people’s favorite examples of existence proofs that show that a set is not empty by showing that its cardinality is odd?
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
This might have been one of the things that prompted the question, but I think Don Zagier’s one-sentence proof of Fermat’s theorem on sums of two squares ( https://en.wikipedia.org/wiki/Proofs_of_Fermat%27s_theorem_on_sums_of_two_squares#Zagier's_"one-sentence_proof") uses this technique! Given a prime p = 4k+1, it defines a finite set S and two involutions. One involution’s fixed points (if they exist) are representations of p as a sum of two squares, while the other has exactly one fixed point. But replacing one involution with another either adds or removes fixed points in pairs, so the first involution has an odd and thus nonzero number of fixed points. (It may be too early for me to do math properly, but it seems like the second involution also shows that S has an odd number of elements, and so the first involution must have an odd number of fixed points?) (On a related note, in case anyone hasn’t seen it, https://mathoverflow.net/a/299696 has a nice geometric method of showing where the involution comes from!) --Neil Bickford On Wed, Jan 29, 2020 at 9:46 AM James Propp <jamespropp@gmail.com> wrote:
Sounds interesting. Do you have a reference?
Jim
On Wed, Jan 29, 2020 at 11:21 AM Cris Moore via math-fun < math-fun@mailman.xmission.com> wrote:
Maybe this is not quite what you want - but Another Hamiltoniain Path
says
that if there is a Hamiltonian path in G, then there is another one either in G or its complement \bar{G}.
The idea is to define an (exponentially large) graph in which Hamiltonian paths correspond to the number of odd-degree vertices. There are an even number of these.
So… this is sorta an example of odd parity, but it’s really showing that the set plus one has even parity :-)
Cris
On Jan 29, 2020, at 7:44 AM, James Propp <jamespropp@gmail.com> wrote:
What are people’s favorite examples of existence proofs that show that a set is not empty by showing that its cardinality is odd?
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
That “windmill” proof is beautiful! This is too easy, but one could also consider the fact that any polynomial of odd degree (and real coefficients) has at least one real root... - Cris
On Jan 29, 2020, at 11:03 AM, Neil Bickford <techie314@gmail.com> wrote:
This might have been one of the things that prompted the question, but I think Don Zagier’s one-sentence proof of Fermat’s theorem on sums of two squares ( https://en.wikipedia.org/wiki/Proofs_of_Fermat%27s_theorem_on_sums_of_two_squares#Zagier's_"one-sentence_proof") uses this technique! Given a prime p = 4k+1, it defines a finite set S and two involutions. One involution’s fixed points (if they exist) are representations of p as a sum of two squares, while the other has exactly one fixed point. But replacing one involution with another either adds or removes fixed points in pairs, so the first involution has an odd and thus nonzero number of fixed points. (It may be too early for me to do math properly, but it seems like the second involution also shows that S has an odd number of elements, and so the first involution must have an odd number of fixed points?)
(On a related note, in case anyone hasn’t seen it, https://mathoverflow.net/a/299696 has a nice geometric method of showing where the involution comes from!)
--Neil Bickford
On Wed, Jan 29, 2020 at 9:46 AM James Propp <jamespropp@gmail.com> wrote:
Sounds interesting. Do you have a reference?
Jim
On Wed, Jan 29, 2020 at 11:21 AM Cris Moore via math-fun < math-fun@mailman.xmission.com> wrote:
Maybe this is not quite what you want - but Another Hamiltoniain Path
says
that if there is a Hamiltonian path in G, then there is another one either in G or its complement \bar{G}.
The idea is to define an (exponentially large) graph in which Hamiltonian paths correspond to the number of odd-degree vertices. There are an even number of these.
So… this is sorta an example of odd parity, but it’s really showing that the set plus one has even parity :-)
Cris
On Jan 29, 2020, at 7:44 AM, James Propp <jamespropp@gmail.com> wrote:
What are people’s favorite examples of existence proofs that show that a set is not empty by showing that its cardinality is odd?
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Cris Moore moore@santafe.edu
On 30/01/2020 23:16, Cris Moore via math-fun wrote:
This is too easy, but one could also consider the fact that any polynomial of odd degree (and real coefficients) has at least one real root...
Is there a parity-based proof of that that isn't strictly inferior to "f(-large) and f(+large) are large and of opposite sign, so by the intermediate value theorem there's a root somewhere between"? -- g
On 31 Jan 2020 at 0:18, Gareth McCaughan wrote:
On 30/01/2020 23:16, Cris Moore via math-fun wrote:
This is too easy, but one could also consider the fact that any polynomial of odd degree (and real coefficients) has at least one real root...
Is there a parity-based proof of that that isn't strictly inferior to "f(-large) and f(+large) are large and of opposite sign, so by the intermediate value theorem there's a root somewhere between"?
Is it not sufficient to show that complex roots always come in pairs, and so when you've exhausted all the complex roots there must be [at least] one more? /Bernie\ Bernie Cosell bernie@fantasyfarm.com -- Too many people; too few sheep --
Right. If you want to be fancy about it, consider a polynomial mod p of degree p+1. It has at least one root in the integers mod p, because the “complex roots” (those that live in field extensions) come in orbits of the Frobenius automorphism (the analog of taking the complex conjugate) of size p. Of course, one could also say that using the opposite signs of f(-large) and f(+large) is a parity-based proof, since it shows that we have to cross the x-axis an odd number of times :-) (counting multiple roots properly of course) C
On Jan 30, 2020, at 5:41 PM, Bernie Cosell <bernie@fantasyfarm.com> wrote:
On 31 Jan 2020 at 0:18, Gareth McCaughan wrote:
On 30/01/2020 23:16, Cris Moore via math-fun wrote:
This is too easy, but one could also consider the fact that any polynomial of odd degree (and real coefficients) has at least one real root...
Is there a parity-based proof of that that isn't strictly inferior to "f(-large) and f(+large) are large and of opposite sign, so by the intermediate value theorem there's a root somewhere between"?
Is it not sufficient to show that complex roots always come in pairs, and so when you've exhausted all the complex roots there must be [at least] one more?
/Bernie\
Bernie Cosell bernie@fantasyfarm.com -- Too many people; too few sheep --
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Cris Moore moore@santafe.edu "It is bound to be very imperfect. But I think it possible that I have got my statues against the sky.” — Virginia Woolf
On 31/01/2020 00:41, Bernie Cosell wrote:
On 31 Jan 2020 at 0:18, Gareth McCaughan wrote:
On 30/01/2020 23:16, Cris Moore via math-fun wrote:
This is too easy, but one could also consider the fact that any polynomial of odd degree (and real coefficients) has at least one real root...
Is there a parity-based proof of that that isn't strictly inferior to "f(-large) and f(+large) are large and of opposite sign, so by the intermediate value theorem there's a root somewhere between"?
Is it not sufficient to show that complex roots always come in pairs, and so when you've exhausted all the complex roots there must be [at least] one more?
Of course -- but for that you must first have proved the "fundamental theorem of algebra", to establish that the number of complex roots equals the degree of the polynomial. And you need the slight extra subtlety of counting by multiplicity. It seems to me that the prerequisites for the parity-based proof are much harder than the sign-change proof is by itself. -- g
I like the image of a bowl of spaghetti with one spaghetti-end sticking out of the mass of pasta. Spaghetti-ends come in pairs, so you know there’s got to be another one somewhere in there! Jim Propp On Fri, Jan 31, 2020 at 5:06 AM Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 31/01/2020 00:41, Bernie Cosell wrote:
On 31 Jan 2020 at 0:18, Gareth McCaughan wrote:
On 30/01/2020 23:16, Cris Moore via math-fun wrote:
This is too easy, but one could also consider the fact that any polynomial of odd degree (and real coefficients) has at least one real root...
Is there a parity-based proof of that that isn't strictly inferior to "f(-large) and f(+large) are large and of opposite sign, so by the intermediate value theorem there's a root somewhere between"?
Is it not sufficient to show that complex roots always come in pairs, and so when you've exhausted all the complex roots there must be [at least] one more?
Of course -- but for that you must first have proved the "fundamental theorem of algebra", to establish that the number of complex roots equals the degree of the polynomial. And you need the slight extra subtlety of counting by multiplicity. It seems to me that the prerequisites for the parity-based proof are much harder than the sign-change proof is by itself.
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I like the image of a bowl of spaghetti with one spaghetti-end sticking out of the mass of pasta. Spaghetti-ends come in pairs, so you know there’s got to be another one somewhere in there!
Jim Propp
Jim, your spaghetti image made me think of the classic graph theory problem on whether it is possible to traverse every edge of a graph and return to your starting point. That requires each vertex to be of even degree, since the if a path goes in it must be able to go out. An odd degree is a piece of spaghetti that can’t connect to anything. I wasn’t initially planning on bringing up this example thinking it was too trivial and obvious for this group. But the spaghetti image forced me to bring it up! Steve On Jan 31, 2020, at 8:36 AM, James Propp <jamespropp@gmail.com<mailto:jamespropp@gmail.com>> wrote: I like the image of a bowl of spaghetti with one spaghetti-end sticking out of the mass of pasta. Spaghetti-ends come in pairs, so you know there’s got to be another one somewhere in there! Jim Propp On Fri, Jan 31, 2020 at 5:06 AM Gareth McCaughan <gareth.mccaughan@pobox.com<mailto:gareth.mccaughan@pobox.com>> wrote: On 31/01/2020 00:41, Bernie Cosell wrote: On 31 Jan 2020 at 0:18, Gareth McCaughan wrote: On 30/01/2020 23:16, Cris Moore via math-fun wrote: This is too easy, but one could also consider the fact that any polynomial of odd degree (and real coefficients) has at least one real root... Is there a parity-based proof of that that isn't strictly inferior to "f(-large) and f(+large) are large and of opposite sign, so by the intermediate value theorem there's a root somewhere between"? Is it not sufficient to show that complex roots always come in pairs, and so when you've exhausted all the complex roots there must be [at least] one more? Of course -- but for that you must first have proved the "fundamental theorem of algebra", to establish that the number of complex roots equals the degree of the polynomial. And you need the slight extra subtlety of counting by multiplicity. It seems to me that the prerequisites for the parity-based proof are much harder than the sign-change proof is by itself. -- g _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com<mailto:math-fun@mailman.xmission.com> https://urldefense.proofpoint.com/v2/url?u=https-3A__mailman.xmission.com_cg... _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com<mailto:math-fun@mailman.xmission.com> https://urldefense.proofpoint.com/v2/url?u=https-3A__mailman.xmission.com_cg...
yes. indeed there is a complexity class PPA (“Polynomial Parity Argument”) of problems like Another Hamiltonian Path where we are given one one odd-degree vertex in a graph and we then know that another one exists. It turns out that we can always reduce such arguments to graphs where the maximum degree is 2, so that the graph consists of open and closed spaghetti strands (plus maybe a few degree-zero two meatballs). - Cris
On Jan 31, 2020, at 6:36 AM, James Propp <jamespropp@gmail.com> wrote:
I like the image of a bowl of spaghetti with one spaghetti-end sticking out of the mass of pasta. Spaghetti-ends come in pairs, so you know there’s got to be another one somewhere in there!
Jim Propp
On Fri, Jan 31, 2020 at 5:06 AM Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 31/01/2020 00:41, Bernie Cosell wrote:
On 31 Jan 2020 at 0:18, Gareth McCaughan wrote:
On 30/01/2020 23:16, Cris Moore via math-fun wrote:
This is too easy, but one could also consider the fact that any polynomial of odd degree (and real coefficients) has at least one real root...
Is there a parity-based proof of that that isn't strictly inferior to "f(-large) and f(+large) are large and of opposite sign, so by the intermediate value theorem there's a root somewhere between"?
Is it not sufficient to show that complex roots always come in pairs, and so when you've exhausted all the complex roots there must be [at least] one more?
Of course -- but for that you must first have proved the "fundamental theorem of algebra", to establish that the number of complex roots equals the degree of the polynomial. And you need the slight extra subtlety of counting by multiplicity. It seems to me that the prerequisites for the parity-based proof are much harder than the sign-change proof is by itself.
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Cris Moore moore@santafe.edu
Here's a Mathologer video of the "windmill proof": https://www.youtube.com/watch?v=DjI1NICfjOk Tom Cris Moore via math-fun writes:
That “windmill” proof is beautiful!
This is too easy, but one could also consider the fact that any polynomial of odd degree (and real coefficients) has at least one real root...
- Cris
On Jan 29, 2020, at 11:03 AM, Neil Bickford <techie314@gmail.com> wrote:
This might have been one of the things that prompted the question, but I think Don Zagier’s one-sentence proof of Fermat’s theorem on sums of two squares ( https://en.wikipedia.org/wiki/Proofs_of_Fermat%27s_theorem_on_sums_of_two_squares#Zagier's_"one-sentence_proof") uses this technique! Given a prime p = 4k+1, it defines a finite set S and two involutions. One involution’s fixed points (if they exist) are representations of p as a sum of two squares, while the other has exactly one fixed point. But replacing one involution with another either adds or removes fixed points in pairs, so the first involution has an odd and thus nonzero number of fixed points. (It may be too early for me to do math properly, but it seems like the second involution also shows that S has an odd number of elements, and so the first involution must have an odd number of fixed points?)
(On a related note, in case anyone hasn’t seen it, https://mathoverflow.net/a/299696 has a nice geometric method of showing where the involution comes from!)
--Neil Bickford
On Wed, Jan 29, 2020 at 9:46 AM James Propp <jamespropp@gmail.com> wrote:
Sounds interesting. Do you have a reference?
Jim
On Wed, Jan 29, 2020 at 11:21 AM Cris Moore via math-fun < math-fun@mailman.xmission.com> wrote:
Maybe this is not quite what you want - but Another Hamiltoniain Path
says
that if there is a Hamiltonian path in G, then there is another one either in G or its complement \bar{G}.
The idea is to define an (exponentially large) graph in which Hamiltonian paths correspond to the number of odd-degree vertices. There are an even number of these.
So… this is sorta an example of odd parity, but it’s really showing that the set plus one has even parity :-)
Cris
On Jan 29, 2020, at 7:44 AM, James Propp <jamespropp@gmail.com> wrote:
What are people’s favorite examples of existence proofs that show that a set is not empty by showing that its cardinality is odd?
Jim Propp
Yes, that’s one of the best examples I know. I plan to include a link to the in my essay. Jim On Mon, Apr 20, 2020 at 11:17 AM Tom Karzes <karzes@sonic.net> wrote:
Here's a Mathologer video of the "windmill proof":
https://www.youtube.com/watch?v=DjI1NICfjOk
Tom
Cris Moore via math-fun writes:
That “windmill” proof is beautiful!
This is too easy, but one could also consider the fact that any
polynomial of odd degree (and real coefficients) has at least one real root...
- Cris
On Jan 29, 2020, at 11:03 AM, Neil Bickford <techie314@gmail.com>
wrote:
This might have been one of the things that prompted the question,
but I
think Don Zagier’s one-sentence proof of Fermat’s theorem on sums of two squares (
https://en.wikipedia.org/wiki/Proofs_of_Fermat%27s_theorem_on_sums_of_two_squares#Zagier's_ "one-sentence_proof")
uses this technique! Given a prime p = 4k+1, it defines a finite set S and two involutions. One involution’s fixed points (if they exist) are representations of p as a sum of two squares, while the other has exactly one fixed point. But replacing one involution with another either adds or removes fixed points in pairs, so the first involution has an odd and thus nonzero number of fixed points. (It may be too early for me to do math properly, but it seems like the second involution also shows that S has an odd number of elements, and so the first involution must have an odd number of fixed points?)
(On a related note, in case anyone hasn’t seen it, https://mathoverflow.net/a/299696 has a nice geometric method of showing where the involution comes from!)
--Neil Bickford
On Wed, Jan 29, 2020 at 9:46 AM James Propp <jamespropp@gmail.com> wrote:
Sounds interesting. Do you have a reference?
Jim
On Wed, Jan 29, 2020 at 11:21 AM Cris Moore via math-fun < math-fun@mailman.xmission.com> wrote:
Maybe this is not quite what you want - but Another Hamiltoniain
Path says
that if there is a Hamiltonian path in G, then there is another one either in G or its complement \bar{G}.
The idea is to define an (exponentially large) graph in which Hamiltonian paths correspond to the number of odd-degree vertices. There are an even number of these.
So… this is sorta an example of odd parity, but it’s really showing that the set plus one has even parity :-)
Cris
On Jan 29, 2020, at 7:44 AM, James Propp <jamespropp@gmail.com> wrote:
What are people’s favorite examples of existence proofs that show that a set is not empty by showing that its cardinality is odd?
Jim Propp
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
With apologies, I suggest Section 6.7.2 of my book The Nature of Computation :-) the original papers, which are also excellent, are: Nimrod Megiddo and Christos H. Papadimitriou. On total functions, existence theorems and computational complexity. Theoretical Computer Science, 81(2):317–324, 1991. Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences, 48(3):498–532, 1994. BTW another nice fact is that the number of Hamiltonian cycles of a graph where all vertices have odd degree is always even. But your original question still stands: sets that are really odd. Another pseudoexample is the number of nonempty subsets of a finite set, but this is again really a set of even size with one element (the empty set) removed… - Cris
On Jan 29, 2020, at 10:45 AM, James Propp <jamespropp@gmail.com> wrote:
Sounds interesting. Do you have a reference?
Jim
On Wed, Jan 29, 2020 at 11:21 AM Cris Moore via math-fun < math-fun@mailman.xmission.com> wrote:
Maybe this is not quite what you want - but Another Hamiltoniain Path says that if there is a Hamiltonian path in G, then there is another one either in G or its complement \bar{G}.
The idea is to define an (exponentially large) graph in which Hamiltonian paths correspond to the number of odd-degree vertices. There are an even number of these.
So… this is sorta an example of odd parity, but it’s really showing that the set plus one has even parity :-)
Cris
On Jan 29, 2020, at 7:44 AM, James Propp <jamespropp@gmail.com> wrote:
What are people’s favorite examples of existence proofs that show that a set is not empty by showing that its cardinality is odd?
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Cris Moore moore@santafe.edu
<< Another pseudoexample is the number of nonempty subsets of a finite set, ... >> --- of a nonempty finite set, perhaps? WFL On 1/29/20, Cris Moore via math-fun <math-fun@mailman.xmission.com> wrote:
With apologies, I suggest Section 6.7.2 of my book The Nature of Computation :-) the original papers, which are also excellent, are:
Nimrod Megiddo and Christos H. Papadimitriou. On total functions, existence theorems and computational complexity. Theoretical Computer Science, 81(2):317–324, 1991.
Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences, 48(3):498–532, 1994.
BTW another nice fact is that the number of Hamiltonian cycles of a graph where all vertices have odd degree is always even.
But your original question still stands: sets that are really odd. Another pseudoexample is the number of nonempty subsets of a finite set, but this is again really a set of even size with one element (the empty set) removed…
- Cris
On Jan 29, 2020, at 10:45 AM, James Propp <jamespropp@gmail.com> wrote:
Sounds interesting. Do you have a reference?
Jim
On Wed, Jan 29, 2020 at 11:21 AM Cris Moore via math-fun < math-fun@mailman.xmission.com> wrote:
Maybe this is not quite what you want - but Another Hamiltoniain Path says that if there is a Hamiltonian path in G, then there is another one either in G or its complement \bar{G}.
The idea is to define an (exponentially large) graph in which Hamiltonian paths correspond to the number of odd-degree vertices. There are an even number of these.
So… this is sorta an example of odd parity, but it’s really showing that the set plus one has even parity :-)
Cris
On Jan 29, 2020, at 7:44 AM, James Propp <jamespropp@gmail.com> wrote:
What are people’s favorite examples of existence proofs that show that a set is not empty by showing that its cardinality is odd?
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Cris Moore moore@santafe.edu
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
And though it's irrelevant to Jim's question, I'm irresistably reminded of the proof by induction that all horses are the same colour(s): plainly true for n = 1 horse; for n > 1 , remove each horse in turn and invoke case n-1 on the remaining subset. QED ... On 1/29/20, Fred Lunnon <fred.lunnon@gmail.com> wrote:
<< Another pseudoexample is the number of nonempty subsets of a finite set, ... >>
--- of a nonempty finite set, perhaps? WFL
On 1/29/20, Cris Moore via math-fun <math-fun@mailman.xmission.com> wrote:
With apologies, I suggest Section 6.7.2 of my book The Nature of Computation :-) the original papers, which are also excellent, are:
Nimrod Megiddo and Christos H. Papadimitriou. On total functions, existence theorems and computational complexity. Theoretical Computer Science, 81(2):317–324, 1991.
Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences, 48(3):498–532, 1994.
BTW another nice fact is that the number of Hamiltonian cycles of a graph where all vertices have odd degree is always even.
But your original question still stands: sets that are really odd. Another pseudoexample is the number of nonempty subsets of a finite set, but this is again really a set of even size with one element (the empty set) removed…
- Cris
On Jan 29, 2020, at 10:45 AM, James Propp <jamespropp@gmail.com> wrote:
Sounds interesting. Do you have a reference?
Jim
On Wed, Jan 29, 2020 at 11:21 AM Cris Moore via math-fun < math-fun@mailman.xmission.com> wrote:
Maybe this is not quite what you want - but Another Hamiltoniain Path says that if there is a Hamiltonian path in G, then there is another one either in G or its complement \bar{G}.
The idea is to define an (exponentially large) graph in which Hamiltonian paths correspond to the number of odd-degree vertices. There are an even number of these.
So… this is sorta an example of odd parity, but it’s really showing that the set plus one has even parity :-)
Cris
On Jan 29, 2020, at 7:44 AM, James Propp <jamespropp@gmail.com> wrote:
What are people’s favorite examples of existence proofs that show that a set is not empty by showing that its cardinality is odd?
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Cris Moore moore@santafe.edu
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Zagier’s proof was indeed the inspiration for my post, along the proof that -1 is a quadratic resodue mod p=4k+1, and Sperner’s Lemma. I am wondering whether a collection of examples of this kind of proof might make a fun Mathematical Enchantments piece sometime. Jim On Wed, Jan 29, 2020 at 2:33 PM Fred Lunnon <fred.lunnon@gmail.com> wrote:
And though it's irrelevant to Jim's question, I'm irresistably reminded of the proof by induction that all horses are the same colour(s): plainly true for n = 1 horse; for n > 1 , remove each horse in turn and invoke case n-1 on the remaining subset. QED ...
On 1/29/20, Fred Lunnon <fred.lunnon@gmail.com> wrote:
<< Another pseudoexample is the number of nonempty subsets of a finite set, ... >>
--- of a nonempty finite set, perhaps? WFL
On 1/29/20, Cris Moore via math-fun <math-fun@mailman.xmission.com> wrote:
With apologies, I suggest Section 6.7.2 of my book The Nature of Computation :-) the original papers, which are also excellent, are:
Nimrod Megiddo and Christos H. Papadimitriou. On total functions, existence theorems and computational complexity. Theoretical Computer Science, 81(2):317–324, 1991.
Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences, 48(3):498–532, 1994.
BTW another nice fact is that the number of Hamiltonian cycles of a graph where all vertices have odd degree is always even.
But your original question still stands: sets that are really odd. Another pseudoexample is the number of nonempty subsets of a finite set, but this is again really a set of even size with one element (the empty set) removed…
- Cris
On Jan 29, 2020, at 10:45 AM, James Propp <jamespropp@gmail.com> wrote:
Sounds interesting. Do you have a reference?
Jim
On Wed, Jan 29, 2020 at 11:21 AM Cris Moore via math-fun < math-fun@mailman.xmission.com> wrote:
Maybe this is not quite what you want - but Another Hamiltoniain Path says that if there is a Hamiltonian path in G, then there is another one either in G or its complement \bar{G}.
The idea is to define an (exponentially large) graph in which Hamiltonian paths correspond to the number of odd-degree vertices. There are an even number of these.
So… this is sorta an example of odd parity, but it’s really showing that the set plus one has even parity :-)
Cris
On Jan 29, 2020, at 7:44 AM, James Propp <jamespropp@gmail.com>
wrote:
What are people’s favorite examples of existence proofs that show
that
a set is not empty by showing that its cardinality is odd?
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Cris Moore moore@santafe.edu
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
True. the number of nonempty subsets of an empty set is even :-) C
On Jan 29, 2020, at 12:20 PM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
<< Another pseudoexample is the number of nonempty subsets of a finite set, ... >>
--- of a nonempty finite set, perhaps? WFL
On 1/29/20, Cris Moore via math-fun <math-fun@mailman.xmission.com> wrote:
With apologies, I suggest Section 6.7.2 of my book The Nature of Computation :-) the original papers, which are also excellent, are:
Nimrod Megiddo and Christos H. Papadimitriou. On total functions, existence theorems and computational complexity. Theoretical Computer Science, 81(2):317–324, 1991.
Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences, 48(3):498–532, 1994.
BTW another nice fact is that the number of Hamiltonian cycles of a graph where all vertices have odd degree is always even.
But your original question still stands: sets that are really odd. Another pseudoexample is the number of nonempty subsets of a finite set, but this is again really a set of even size with one element (the empty set) removed…
- Cris
On Jan 29, 2020, at 10:45 AM, James Propp <jamespropp@gmail.com> wrote:
Sounds interesting. Do you have a reference?
Jim
On Wed, Jan 29, 2020 at 11:21 AM Cris Moore via math-fun < math-fun@mailman.xmission.com> wrote:
Maybe this is not quite what you want - but Another Hamiltoniain Path says that if there is a Hamiltonian path in G, then there is another one either in G or its complement \bar{G}.
The idea is to define an (exponentially large) graph in which Hamiltonian paths correspond to the number of odd-degree vertices. There are an even number of these.
So… this is sorta an example of odd parity, but it’s really showing that the set plus one has even parity :-)
Cris
On Jan 29, 2020, at 7:44 AM, James Propp <jamespropp@gmail.com> wrote:
What are people’s favorite examples of existence proofs that show that a set is not empty by showing that its cardinality is odd?
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Cris Moore moore@santafe.edu
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Cris Moore moore@santafe.edu
On 29/01/2020 14:44, James Propp wrote:
What are people’s favorite examples of existence proofs that show that a set is not empty by showing that its cardinality is odd?
Not exactly parity, but very much in the same mental pigeonhole: a group whose order is a multiple of p has an element of order p. Proof: consider p-tuples of elements whose product is 1. There are |G|^(p-1) of these because we can pick the first p-1 things in the tuple freely and then the last one is the inverse of their product. This is a multiple of p. The number of such tuples whose elements _aren't_ all equal is a multiple of p because we can permute cyclically. So the number whose elements _are_ all equal -- i.e., the number of elements of order 1 or p -- is also a multiple of p. And it's not 0 because of (1,...,1), so the number of elements of order p is p-1 (mod p) and in particular is nonzero. -- g
Not exactly parity, but very much in the same mental pigeonhole: a group whose order is a multiple of p has an element of order p. Proof: consider p-tuples of elements whose product is 1. There are |G|^(p-1) of these because we can pick the first p-1 things in the tuple freely and then the last one is the inverse of their product. This is a multiple of p. The number of such tuples whose elements _aren't_ all equal is a multiple of p because we can permute cyclically.
This doesn't quite work here; there are also p-tuples that are periodic with period of a factor of p. For instance, mod 10, using 6-tuples: (1,2,2,1,2,2). There are only three unique cyclic permutations of this 6-tuple. -- -- http://cube20.org/ -- http://golly.sf.net/ --
I think p was chosen to imply it had to be prime :-) On Fri, Jan 31, 2020 at 1:02 PM Tomas Rokicki <rokicki@gmail.com> wrote:
Not exactly parity, but very much in the same mental pigeonhole: a group whose order is a multiple of p has an element of order p. Proof: consider p-tuples of elements whose product is 1. There are |G|^(p-1) of these because we can pick the first p-1 things in the tuple freely and then the last one is the inverse of their product. This is a multiple of p. The number of such tuples whose elements _aren't_ all equal is a multiple of p because we can permute cyclically.
This doesn't quite work here; there are also p-tuples that are periodic with period of a factor of p. For instance, mod 10, using 6-tuples: (1,2,2,1,2,2). There are only three unique cyclic permutations of this 6-tuple.
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
I believe the argument for prime p. On Fri, Jan 31, 2020 at 10:13 AM Michael Kleber <michael.kleber@gmail.com> wrote:
I think p was chosen to imply it had to be prime :-)
On Fri, Jan 31, 2020 at 1:02 PM Tomas Rokicki <rokicki@gmail.com> wrote:
Not exactly parity, but very much in the same mental pigeonhole: a group whose order is a multiple of p has an element of order p. Proof: consider p-tuples of elements whose product is 1. There are |G|^(p-1) of these because we can pick the first p-1 things in the tuple freely and then the last one is the inverse of their product. This is a multiple of p. The number of such tuples whose elements _aren't_ all equal is a multiple of p because we can permute cyclically.
This doesn't quite work here; there are also p-tuples that are periodic with period of a factor of p. For instance, mod 10, using 6-tuples: (1,2,2,1,2,2). There are only three unique cyclic permutations of this 6-tuple.
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
On 31/01/2020 18:01, Tomas Rokicki wrote: [me:]
Not exactly parity, but very much in the same mental pigeonhole: a group whose order is a multiple of p has an element of order p. Proof: consider p-tuples of elements whose product is 1. There are |G|^(p-1) of these because we can pick the first p-1 things in the tuple freely and then the last one is the inverse of their product. This is a multiple of p. The number of such tuples whose elements _aren't_ all equal is a multiple of p because we can permute cyclically.
[Tom:]
This doesn't quite work here; there are also p-tuples that are periodic with period of a factor of p. For instance, mod 10, using 6-tuples: (1,2,2,1,2,2). There are only three unique cyclic permutations of this 6-tuple.
As others have said, I intended the name "p" to imply primality. Sorry if that wasn't clear. -- g
This is a parity argument in the case where p = 2, where it simplifies to: In a group of even order, elements that are not their own inverse come in inverse pairs. That leaves an even number of elements that are there own inverses, which include the identity and an odd (and therefore nonzero) number of elements of order 2. Andy On Wed, Jan 29, 2020 at 6:34 PM Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 29/01/2020 14:44, James Propp wrote:
What are people’s favorite examples of existence proofs that show that a set is not empty by showing that its cardinality is odd?
Not exactly parity, but very much in the same mental pigeonhole: a group whose order is a multiple of p has an element of order p. Proof: consider p-tuples of elements whose product is 1. There are |G|^(p-1) of these because we can pick the first p-1 things in the tuple freely and then the last one is the inverse of their product. This is a multiple of p. The number of such tuples whose elements _aren't_ all equal is a multiple of p because we can permute cyclically. So the number whose elements _are_ all equal -- i.e., the number of elements of order 1 or p -- is also a multiple of p. And it's not 0 because of (1,...,1), so the number of elements of order p is p-1 (mod p) and in particular is nonzero.
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
Emergency room doctor's rule. If a gunshot victim has an odd number of bullet holes in his/her body, there remains a bullet that has to be removed. On Fri, Jan 31, 2020 at 4:06 PM Andy Latto <andy.latto@pobox.com> wrote:
This is a parity argument in the case where p = 2, where it simplifies to:
In a group of even order, elements that are not their own inverse come in inverse pairs. That leaves an even number of elements that are there own inverses, which include the identity and an odd (and therefore nonzero) number of elements of order 2.
Andy
On Wed, Jan 29, 2020 at 6:34 PM Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 29/01/2020 14:44, James Propp wrote:
What are people’s favorite examples of existence proofs that show that
a
set is not empty by showing that its cardinality is odd?
Not exactly parity, but very much in the same mental pigeonhole: a group whose order is a multiple of p has an element of order p. Proof: consider p-tuples of elements whose product is 1. There are |G|^(p-1) of these because we can pick the first p-1 things in the tuple freely and then the last one is the inverse of their product. This is a multiple of p. The number of such tuples whose elements _aren't_ all equal is a multiple of p because we can permute cyclically. So the number whose elements _are_ all equal -- i.e., the number of elements of order 1 or p -- is also a multiple of p. And it's not 0 because of (1,...,1), so the number of elements of order p is p-1 (mod p) and in particular is nonzero.
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
For the Square Peg Problem https://en.wikipedia.org/wiki/Inscribed_square_problem, if the curve is piecewise smooth, the argument shows that there is an odd number of inscribed squares (generically). https://www.ams.org/notices/201404/rnoti-p346.pdf James On Wed, Jan 29, 2020 at 2:45 PM James Propp <jamespropp@gmail.com> wrote:
What are people’s favorite examples of existence proofs that show that a set is not empty by showing that its cardinality is odd?
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- James
It seems that the Conway-Gordon theorem is another example: the authors prove that, given 6 points in general position in R^3, the number of ways [out of (6 choose 3)/2 == 10] to partition them into two *linked* triangles is necessarily odd. https://twitter.com/JSEllenberg/status/1250585677202325505
Sent: Friday, January 31, 2020 at 6:45 PM From: "James Aaronson" <jamesaaaronson@gmail.com> To: "math-fun" <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Existence from parity
For the Square Peg Problem https://en.wikipedia.org/wiki/Inscribed_square_problem, if the curve is piecewise smooth, the argument shows that there is an odd number of inscribed squares (generically).
https://www.ams.org/notices/201404/rnoti-p346.pdf
James
On Wed, Jan 29, 2020 at 2:45 PM James Propp <jamespropp@gmail.com> wrote:
What are people’s favorite examples of existence proofs that show that a set is not empty by showing that its cardinality is odd?
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- James _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Thanks! Jim On Thu, Apr 16, 2020 at 7:24 AM Adam P. Goucher <apgoucher@gmx.com> wrote:
It seems that the Conway-Gordon theorem is another example: the authors prove that, given 6 points in general position in R^3, the number of ways [out of (6 choose 3)/2 == 10] to partition them into two *linked* triangles is necessarily odd.
https://twitter.com/JSEllenberg/status/1250585677202325505
Sent: Friday, January 31, 2020 at 6:45 PM From: "James Aaronson" <jamesaaaronson@gmail.com> To: "math-fun" <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Existence from parity
For the Square Peg Problem https://en.wikipedia.org/wiki/Inscribed_square_problem, if the curve is piecewise smooth, the argument shows that there is an odd number of inscribed squares (generically).
https://www.ams.org/notices/201404/rnoti-p346.pdf
James
On Wed, Jan 29, 2020 at 2:45 PM James Propp <jamespropp@gmail.com> wrote:
What are people’s favorite examples of existence proofs that show that a set is not empty by showing that its cardinality is odd?
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- James _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Right, but this is different from some of the pairing proofs we talked about before. The paper is here : http://people.reed.edu/~ormsbyk/138/ConwayGordon.pdf <http://people.reed.edu/~ormsbyk/138/ConwayGordon.pdf> They show that the sum mod 2 of the number of linked pairs of triangles is the same for all embeddings since it’s invariant under crossing changes, and then they show that it is 1 for a particular embedding. C
On Apr 16, 2020, at 5:24 AM, Adam P. Goucher <apgoucher@gmx.com> wrote:
It seems that the Conway-Gordon theorem is another example: the authors prove that, given 6 points in general position in R^3, the number of ways [out of (6 choose 3)/2 == 10] to partition them into two *linked* triangles is necessarily odd.
https://twitter.com/JSEllenberg/status/1250585677202325505
Sent: Friday, January 31, 2020 at 6:45 PM From: "James Aaronson" <jamesaaaronson@gmail.com> To: "math-fun" <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Existence from parity
For the Square Peg Problem https://en.wikipedia.org/wiki/Inscribed_square_problem, if the curve is piecewise smooth, the argument shows that there is an odd number of inscribed squares (generically).
https://www.ams.org/notices/201404/rnoti-p346.pdf
James
On Wed, Jan 29, 2020 at 2:45 PM James Propp <jamespropp@gmail.com> wrote:
What are people’s favorite examples of existence proofs that show that a set is not empty by showing that its cardinality is odd?
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- James _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (15)
-
Adam P. Goucher -
Andy Latto -
Bernie Cosell -
Cris Moore -
Fred Lunnon -
Gareth McCaughan -
James Aaronson -
James Propp -
Lucas, Stephen K - lucassk -
Michael Kleber -
Neil Bickford -
Tom Karzes -
Tomas Rokicki -
W. Edwin Clark -
Éric Angelini