# Topological Fixed Point Exercises

This is one of three sets of fixed point ex­er­cises. The first post in this se­quence is here, giv­ing con­text.

1. (1-D Sperner’s lemma) Con­sider a path built out of edges as shown. Color each ver­tex blue or green such that the left­most ver­tex is blue and the right­most ver­tex is green. Show that an odd num­ber of the edges will be bichro­matic. 1. (In­ter­me­di­ate value the­o­rem) The Bolzano-Weier­strass the­o­rem states that any bounded se­quence in has a con­ver­gent sub­se­quence. The in­ter­me­di­ate value the­o­rem states that if you have a con­tin­u­ous func­tion such that and , then there ex­ists an such that . Prove the in­ter­me­di­ate value the­o­rem. It may be helpful later on if your proof uses 1-D Sperner’s lemma and the Bolzano-Weier­strass the­o­rem.

2. (1-D Brouwer fixed point the­o­rem) Show that any con­tin­u­ous func­tion has a fixed point (i.e. a point with ). Why is this not true for the open in­ter­val ?

3. (2-D Sperner’s lemma) Con­sider a tri­an­gle built out of smaller tri­an­gles as shown. Color each ver­tex red, blue, or green, such that none of the ver­tices on the large bot­tom edge are red, none of the ver­tices on the large left edge are green, and none of the ver­tices on the large right edge are blue. Show that an odd num­ber of the small tri­an­gles will be trichro­matic. 1. Color the all the points in the disk as shown. Let be a con­tin­u­ous func­tion from a closed tri­an­gle to the disk, such that the bot­tom edge is sent to non-red points, the left edge is sent to non-green points, and the right edge is sent to non-blue points. Show that sends some point in the tri­an­gle to the cen­ter. 1. Show that any con­tin­u­ous func­tion from closed tri­an­gle to it­self has a fixed point.

2. (2-D Brouwer fixed point the­o­rem) Show that any con­tin­u­ous func­tion from a com­pact con­vex sub­set of to it­self has a fixed point. (You may use the fact that given any closed con­vex sub­set of , the func­tion from to which pro­jects each point to the near­est point in is well defined and con­tin­u­ous.)

3. Reflect on how non-con­struc­tive all of the above fixed-point find­ings are. Find a pa­ram­e­ter­ized class of func­tions where for each , , and the func­tion is con­tin­u­ous, but there is no con­tin­u­ous way to pick out a sin­gle fixed point from each func­tion (i.e. no con­tin­u­ous func­tion such that is a fixed point of for all ).

4. (Sperner’s lemma) Gen­er­al­ize ex­er­cises 1 and 4 to an ar­bi­trary di­men­sion sim­plex.

5. (Brouwer fixed point the­o­rem) Show that any con­tin­u­ous func­tion from a com­pact con­vex sub­set of to it­self has a fixed point.

6. Given two nonempty com­pact sub­sets , the Haus­dorff dis­tance be­tween them is the supre­mum over all points in ei­ther sub­set of the dis­tance from that point to the other sub­set. We call a set val­ued func­tion a con­tin­u­ous Haus­dorff limit if there is a se­quence of con­tin­u­ous func­tions from to whose graphs, , con­verge to the graph of , , in Haus­dorff dis­tance. Show that ev­ery con­tin­u­ous Haus­dorff limit from a com­pact con­vex sub­set of to it­self has a fixed point (a point such that ).

7. Let and be nonempty com­pact con­vex sub­sets of . We say that a set val­ued func­tion, is a Kaku­tani func­tion if the graph of , , is closed, and is con­vex and nonempty for all . For ex­am­ple, we could take and to be the in­ter­val , and we could have send each to , map to the whole in­ter­val , and map to . Show that ev­ery Kaku­tani func­tion is a con­tin­u­ous Haus­dorff limit. (Hint: Start with the case where is a unit cube. Con­struct by break­ing into small cubes of side length . Con­stuct a smaller cube of side length within each cube. Send each small to the con­vex hull of the images of all points in the cube with a con­tin­u­ous func­tion, and glue these to­gether with straight lines. Make sure you don’t ac­ci­den­tally get ex­tra limit points.)

8. (Kaku­tani fixed point the­o­rem) Show that ev­ery Kaku­tani func­tion from a com­pact con­vex sub­set of to it­self has a fixed point.

Please use the spoilers fea­ture—the sym­bol ‘>’ fol­lowed by ‘!’ fol­lowed by space -in your com­ments to hide all solu­tions, par­tial solu­tions, and other dis­cus­sions of the math. The com­ments will be mod­er­ated strictly to hide spoilers!

I recom­mend putting all the ob­ject level points in spoilers and leav­ing meta­data out­side of the spoilers, like so: “I think I’ve solved prob­lem #5, here’s my solu­tion <spoilers>” or “I’d like help with prob­lem #3, here’s what I un­der­stand <spoilers>” so that peo­ple can choose what to read.

No nominations.
No reviews.
• Proof of #4, but with un­nec­es­sary calcu­lus:

Not only is there an odd num­ber of tri­color tri­an­gles, but they come in pairs ac­cord­ing to their ori­en­ta­tion (RGB clock­wise/​an­ti­clock­wise). Proof: define a con­tin­u­ously differ­en­tiable vec­tor field on the plane, by let­ting the field at each ver­tex be 0, and the field in the cen­ter of each edge be a vec­tor of mag­ni­tude 1 point­ing in the di­rec­tion R->G->B->R (or 0 if the two ad­ja­cent ver­tices are the same color). Ex­tend the field to the com­plete edges, then the in­te­ri­ors of the tri­an­gles by some in­ter­po­la­tion method with con­tin­u­ous deriva­tive (eg. co­sine in­ter­po­la­tion).

As­sume the line in­te­gral along one unit edge in the di­rec­tion R->G or G->B or B->R to be 13. (Without loss of gen­er­al­ity since we can rescale the graph/​vec­tors to make this true). Then a similar par­ity ar­gu­ment to Sperner’s 1d lemma (or the FTC) shows that the clock­wise line in­te­gral along each large edge is 13, hence the line in­te­gral around the large tri­an­gle is 1/​3+1/​3+1/​3=1.

By green’s the­o­rem, this is equal to the in­te­grated curl of the field in the in­te­rior of the large tri­an­gle, and hence equal (by an­other in­vo­ca­tion of green’s the­o­rem) to the summed clock­wise line in­te­grals around each small tri­an­gle. The in­te­grals around a uni­color or bi­color tri­an­gle are 0 and −1/​3 + 13 + 0 = 0 re­spec­tively, leav­ing only tri­color tri­an­gles, whose in­te­gral is again 1 de­pend­ing on ori­en­ta­tion. Thus: (tri­color clock­wise) - (tri­color an­ti­clock­wise) = 1. QED.

• Just to get things started, here’s a proof for #1:

Proof by in­duc­tion that the num­ber of bi­color edges is odd iff the ends don’t match. Base case: a sin­gle node has match­ing ends and an even num­ber (zero) of bi­color edges. Ex­tend­ing with a non-bi­color edge changes nei­ther con­di­tion, and ex­tend­ing with a bi­color edge changes both; in both cases the in­duc­tion hy­poth­e­sis is pre­served.

• Here’s a more con­cep­tual fram­ing:

If we imag­ine blue as la­bel­ling the odd num­bered seg­ments and green as la­bel­ling the even num­bered seg­ments, it is clear that there must be an even num­ber of seg­ments in to­tal. The num­ber of gaps be­tween seg­ments is equal to the num­ber of seg­ments minus 1, so it is odd.

• Clean­est solu­tion I can find for #8:

Also, if we have a proof for #6 there’s a pleas­ant method for #7 that should work in any di­men­sion:

We take our closed con­vex set that has the bounded func­tion . We take a tri­an­gle that cov­ers so that any point in is also in .

Now we define a new func­tion such that where is the func­tion that maps to the near­est point in .

By #6 we know that has a fixed point, since is con­tin­u­ous. We know that the fixed point of can­not lie out­side be­cause the range of is . This means has a fixed point within and since for , , has a fixed point.

• On my ap­proach:

I con­structed a large tri­an­gle around the con­vex shape with the cen­ter some­where in the in­te­rior. I then pro­jected each point in the con­vex shape from the cen­ter to­wards the edge of the tri­an­gle in a pro­por­tional man­ner. ie. The cen­ter stays where it is, the points on the edge of the con­vex shape are pro­jected to the edge of the tri­an­gle and a point 1/​x of the dis­tance from the cen­ter to the edge of the con­vex shape is 1/​x of the dis­tance from the cen­ter to the edge of the tri­an­gle.

• If #4 is true, it is prov­able:

If #4 is true, chang­ing the color of a sin­gle node (ex­cept to for­bid­den col­ors on edges) can­not change the par­ity of the trichro­matic tri­an­gle count, and this would be check­able through a finite case anal­y­sis of graphs of size <=7. Given that lemma, we can re­color one cor­ner to red, the re­main­der of one large edge blue and the re­main­ing nodes green, pro­duc­ing the odd count 1.

#8:

We are look­ing for a sur­face [0,1]²->[0,1] whose in­ter­sec­tion with the plane x=y does not con­tain a func­tion of t. It suffices to show that the in­ter­sec­tion looks like the let­ter s, with ex­actly the end­points reach­ing t=0 or t=1. It suffices to show that the in­ter­sec­tion can be any con­ti­nous func­tion of x in­clud­ing the points t=x=y=0 and t=x=y=1. Within each plane of con­stant x, define the sur­face as 0 for small t, 1 for large t, and rapidly ris­ing through the plane x=y wher­ever we want the in­ter­sec­tion.

• Found a nice proof for Sperner’s lemma (#9):

First some defi­ni­tions. Call a d-sim­plex with ver­tices col­ored in (d+1) differ­ent col­ored chro­matic. Call the par­ity of the num­ber of chro­matic sim­plices the chro­matic par­ity.

It’s eas­ier to prove the fol­low­ing gen­er­al­iza­tion: Take a com­plex of d-sim­plices that form a d-sphere: then any (d+1)-col­or­ing of the ver­tices will have even chro­matic par­ity.

Proof by in­duc­tion on d:

Base d=-1: vac­u­ously true.

As­sume true for d-1: Say you have an ar­bi­trary com­plex of d-sim­plices form­ing a d-sphere, with an ar­bi­trary d+1-col­or­ing. Choose a ver­tex. W.L.O.G. we will call the color of the cho­sen ver­tex blue.

Take the com­plex of sim­plices that con­tain this ver­tex. Since a sphere has no bound­ary or branches, this com­plex will be a d-ball. Delete the cho­sen ver­tex, and keep only the op­po­site (d-1)-sim­plices that are left, which will form a (d-1)-sphere, call it the shell.

We need to choose a sec­ond color, say red. We’ll call a (d-1)-sim­plex with ver­tices of all d+1 col­ors ex­cept red an R-chro­matic face, and similarly with blue.

Now, re­place all the red ver­tices in the shell with blue ver­tices, so that the shell is now R-chro­matic. By in­duc­tion it has an even num­ber of R-chro­matic faces. Con­sider what hap­pens when we re­con­vert a ver­tex on the shell back to red: since the ver­tex was pre­vi­ously blue, any R-chro­matic faces will get turned into B-chro­matic faces. Let r be the num­ber of R-chro­matic faces on the shell, and b be the num­ber of B-chro­matic faces. The par­ity of r-b will re­main even as we con­tinue this pro­cess.

Let’s go back to the ver­tex in the cen­ter of the shell. All cur­rently chro­matic sim­plices with this ver­tex have op­po­site faces which are B-chro­matic, since this ver­tex is blue. We’ll flip the ver­tex to red, which de­stroys chro­matic sim­plices with op­po­site B-chro­matic faces and cre­ates chro­matic sim­plices with op­po­site R-chro­matic faces. Since r-b is even, the chro­matic par­ity is pre­served!

Since we’ve shown that ar­bi­trary re­col­or­ing of ver­tices pre­serves the chro­matic par­ity, it’s clear that the chro­matic par­ity will be even for any col­or­ing.

Corol­lary: Sperner’s lemma

Start with a d-sim­plex which has been di­vided into d-sim­plices, and where each face of the large sim­plex has one color which ver­tices on it are for­bid­den from tak­ing. Take a point of each color, and match it with a face of the sim­plex that that color is al­lowed on. Then con­nect that ver­tex to each point on that face. This will cre­ate a bunch of non-chro­matic sim­plices. Fi­nally, cre­ate a sim­plex of all of the new points. This will cre­ate one chro­matic sim­plex.

This will form a d-sphere, and thus will have an even chro­matic par­ity. That means the origi­nal sim­plex must have had odd chro­matic par­ity.

• Thanks! I find this ap­proach more in­tu­itive than the proof of Sperner’s lemma that I found in Wikipe­dia. Along with nshep­perd’s com­ment, it also in­spired me to work out an in­ter­est­ing ex­ten­sion that re­quires only minor mod­ifi­ca­tions to your proof:

d-spheres are ori­entable man­i­folds, hence so is a de­com­po­si­tion of a d-sphere into a com­plex K of d-sim­plices. So we may ar­bi­trar­ily choose one of the two pos­si­ble ori­en­ta­tions for K (e.g. by choos­ing a par­tic­u­lar sim­plex P in K, or­der­ing its ver­tices from 1 to d + 1, and declar­ing it to be the pro­to­typ­i­cal pos­i­tively ori­ented sim­plex; when d = 2, P could be a tri­an­gle with the ver­tices go­ing around coun­ter­clock­wise when you count from 1 to 3; when d = 3, P could be a tetra­he­dron where, if you po­si­tion your right hand in its cen­ter and point your thumb at the 1-ver­tex, your fingers curl around in the same di­rec­tion in which you count the re­main­ing ver­tices from 2 to 4). Then any or­der­ing of the ver­tices of any d-sim­plex in K may be said to have pos­i­tive or nega­tive ori­en­ta­tion (chiral­ity). (E.g. it would be pos­i­tive when there’s an ori­en­ta­tion-pre­serv­ing map (e.g. a ro­ta­tion) send­ing each of its ver­tices to the cor­re­spond­ingly num­bered ver­tices of P.)

So here’s my ex­ten­sion of par­ent com­ment’s the­o­rem: Any col­or­ing of the ver­tices of K with the col­ors {1, …, d + 1} will con­tain an equal num­ber of pos­i­tively and nega­tively ori­ented chro­matic d-sim­plices—that is, the rea­son the num­ber of chro­matic d-sim­plices in K must be even is that each one can be paired off with one of the op­po­site (mir­ror) ori­en­ta­tion. (Does this the­o­rem have a name? If so I couldn’t find it.)

Fol­low­ing par­ent com­ment, the proof is by in­duc­tion on the di­men­sion d. When d = 1, K is just a cy­cle graph with ver­tices col­ored 1 or 2. As we go around clock­wise (or coun­ter­clock­wise), we must tra­verse an equal num­ber of 1→2 edges and 2→1 edges (i.e. op­po­sitely ori­ented 1-sim­plices), by the time we re­turn to our start­ing point.

Now let d > 1, and as­sume the the­o­rem is true in the (d-1)-di­men­sional case. As in par­ent com­ment, we may choose any ver­tex v of K, and then the faces op­po­site to v in each d-sim­plex in K that con­tains v will, to­gether, form a (d-1)-di­men­sional sub­com­plex K′ of K that is home­o­mor­phic (topolog­i­cally equiv­a­lent) to a (d-1)-sphere.

Sup­pose v has color i. We will show that chang­ing v’s color to ji will add or re­move the same num­ber of pos­i­tively ori­ented chro­matic d-sim­plices as nega­tively ori­ented ones: For­get, for the mo­ment, the dis­tinc­tion be­tween col­ors i and j—say any i or j-col­ored ver­tex of K′ has color “i-or-j.” Then K′ is now d-col­ored, so, by in­duc­tive hy­poth­e­sis, the chro­matic (d-1)-sim­plices of K′ must oc­cur in pairs of op­po­site ori­en­ta­tion (if any ex­ist—if none ex­ist, v can’t be part of any chro­matic d-sim­plex re­gard­less of its color). Con­sider such a pair, call them F₁ and F₂.

Now cease pre­tend­ing that i and j are a sin­gle color. Since F₁ was chro­matic in K′, it must have had an i-or-j–col­ored ver­tex. Sup­pose, WOLOG, that that ver­tex was ac­tu­ally j-col­ored. Then, to­gether with i-col­ored v, F₁ spans a chro­matic d-sim­plex of K, call it S₁, which we may as­sume WOLOG to be pos­i­tively ori­ented. Once we change the color of v from i to j, how­ever, S₁ will have two j-col­ored ver­tices, and so will no longer be chro­matic. To see that bal­ance is main­tained, con­sider what hap­pens with F₂:

If F₂‘s i-or-j–col­ored ver­tex was, like F₁‘s, ac­tu­ally j-col­ored, then the d-sim­plex spanned by F₂ and v, call it S₂, was chro­matic and nega­tively ori­ented (be­cause F₂ had op­po­site ori­en­ta­tion to F₁ in K′), and thus S₂ also ceased to be chro­matic when we changed v’s color from i to j, bal­anc­ing S₁‘s loss of chro­matic sta­tus. Other­wise, F₂‘s i-or-j–col­ored ver­tex must have been i-col­ored, in which case S₂ wasn’t chro­matic when v was also i-col­ored, but chang­ing v’s color to j turned S₂ into a new d-chro­matic sim­plex. But what is S₂‘s ori­en­ta­tion? Well, it was nega­tive un­der the as­sump­tion that S₂‘s i-or-j–col­ored ver­tex was j-col­ored and v was i-col­ored, and swap­ping the la­bels of a pair of ver­tices in an ori­ented sim­plex re­verses its ori­en­ta­tion, so, un­der the pre­sent as­sump­tion, S₂’s ori­en­ta­tion must be pos­i­tive! Thus the loss of S₁ as a pos­i­tively ori­ented chro­matic d-sim­plex is bal­anced by the ad­di­tion of S₂ as a new pos­i­tively ori­ented chro­matic d-sim­plex.

If all of K’s ver­tices are the same color, it has the same num­ber (zero) of pos­i­tively and nega­tively ori­ented chro­matic d-sim­plices, and since this par­ity is pre­served when we change the col­ors of the ver­tices of K one at a time, it re­mains no mat­ter how we (d+1)-color K. ☐

We can re­late this the­o­rem back to Sperner’s lemma us­ing the same trick as par­ent com­ment: Sup­pose we are given a tri­an­gu­la­tion K of a reg­u­lar d-sim­plex S into smaller d-sim­plices, and a (d+1)-col­or­ing of K’s ver­tices that as­signs a unique color to each ver­tex v of S, and doesn’t use that color for any of K’s ver­tices ly­ing on the face of S op­po­site to v. We form a larger sim­pli­cial com­plex L con­tain­ing K by adding d + 1 new ver­tices as fol­lows: For i = 1, …, d + 1, place a new i-col­ored ver­tex ex­te­rior to S, some dis­tance from the cen­ter of S along the ray that goes through the i-col­ored ver­tex of S. Con­nect this new ver­tex to each ver­tex of K ly­ing in the face of S op­po­site from the (i+1)-col­ored (or 1-col­ored, when i = d + 1) ver­tex of S. (Note that none of the d-sim­plices thereby cre­ated will be chro­matic, be­cause they won’t have an (i+1)-col­ored ver­tex.) Then con­nect all of the new ver­tices to each other.

Hav­ing thus defined L, we can em­bed it in a d-sphere, of which it will con­sti­tute a tri­an­gu­la­tion, be­cause the new ver­tices will form a d-sim­plex T whose “in­te­rior” is the com­ple­ment of L in the sphere. Thus we can ap­ply our above the­o­rem to con­clude that L has equally many pos­i­tively and nega­tively ori­ented chro­matic d-sim­plices. By con­struc­tion, none of L’s new ver­tices are in­cluded in any chro­matic d-sim­plex other than T, so K must con­tain an equal num­ber (pos­si­bly zero) of pos­i­tively and nega­tively ori­ented chro­matic d-sim­plices, plus one more, of op­po­site ori­en­ta­tion to T. And what is the ori­en­ta­tion of T? I claim that it is op­po­site to that of S: Con­sider T by it­self, em­bed­ded in the sphere. T’s bound­ary and ex­te­rior (the in­te­rior of L) then con­sti­tute an­other chro­matic d-sim­plex, call it U, which is es­sen­tially just a mag­nifi­ca­tion of S, with cor­re­spond­ingly col­ored ver­tices, and so share’s S’s ori­en­ta­tion. Ap­ply­ing our the­o­rem again, we see that T and U must have op­po­site ori­en­ta­tions*, so we con­clude that K must con­tain ex­actly one more chro­matic d-sim­plex of the same ori­en­ta­tion as S than of the op­po­site ori­en­ta­tion. (As proved in nshep­perd’s com­ment for the case d = 2.)

*The ob­ser­va­tion, that, on the sur­face of a sphere, the in­te­rior and ex­te­rior of a trichro­matic tri­an­gle have op­po­site ori­en­ta­tions, is what sent me down this rab­bit hole in the first place. :)

• Clar­ify­ing ques­tion for #9:

How does the de­com­po­si­tion into seg­ments/​tri­an­gles gen­er­al­ize to 3+ di­men­sions? If you try de­com­pos­ing a tetra­he­dron into mul­ti­ple tetra­he­dra, you ac­tu­ally get 4 tetra­he­dra and 1 oc­ta­he­dron, as shown here.

EDIT: an­swered my own ques­tion:

You can de­com­pose an oc­ta­he­dron into 4 tetra­he­drons. They’re ir­reg­u­lar, but this is ac­tu­ally fine for the pur­pose of the lemma.

• Inap­pro­pri­ately high­brow proof of #4 (2d Sperner’s lemma):

This proves a gen­er­al­iza­tion: any num­ber of di­men­sions, and any tri­an­gu­la­tion of the sim­plex in ques­tion. So, the setup is as fol­lows. We have an n-di­men­sional sim­plex, defined by n+1 points in n-di­men­sional space. We colour the ver­tices with n+1 differ­ent colours. Then we tri­an­gu­late it—chop it up into smaller sim­plexes—and we ex­tend our colour­ing some­how in such a way that the ver­tices on any face (note: a face is the thing spanned by any sub­set of the ver­tices) of the big sim­plex are coloured us­ing only the colours from the ver­tices that span that face. And the task is to prove that there are an odd num­ber of lit­tle sim­plexes whose ver­tices have all n+1 colours.

This colour­ing defines a map from the ver­tices of the tri­an­gu­la­tion to the ver­tices of the big sim­plex: map each tri­an­gu­la­tion-ver­tex to the sim­plex-ver­tex that’s the same colour. We can ex­tend this map to the rest of each lit­tle sim­plex by lin­ear in­ter­po­la­tion. The re­sult­ing thing is con­tin­u­ous on the whole of the big sim­plex, so we have a con­tin­u­ous map (call it f) from the big sim­plex to it­self. And we want to prove that we have an odd num­ber of lit­tle sim­plices whose image un­der f spans the whole thing. (Call these “good” sim­plices.)

We’ll do it with two in­gre­di­ents. The easy one is in­duc­tion: when prov­ing this in n di­men­sions we shall as­sume we already proved it for smaller num­bers of di­men­sions. The harder one is ho­mol­ogy, a stan­dard tool in alge­braic topol­ogy. More pre­cisely we’ll do ho­mol­ogy mod 2. It as­so­ci­ates with each topolog­i­cal space X and each di­men­sion d an abelian group Hd(X), and the key things you need to know are (1) that if you have f : X → Y then you get an as­so­ci­ated group ho­mo­mor­phism f* : Hd(X) → Hd(Y), (2) that Hd(a sim­plex) is the cyclic group of or­der 2 if d=0, and the triv­ial group oth­er­wise, and (3) that Hd(the bound­ary of a sim­plex) is the cyclic group of or­der 2 if d=0 or d = (di­men­sion of sim­plex − 1) and the triv­ial group oth­er­wise. Oh, and one other cru­cial thing: if you have f : X → Y and g : Y → Z then (gf)* = g*f*: com­po­si­tion of maps be­tween topolog­i­cal space cor­re­sponds to com­po­si­tion of ho­mo­mor­phisms be­tween their ho­mol­ogy groups.

(You can do ho­mol­ogy “over” any com­mu­ta­tive ring. The groups you get are ac­tu­ally mod­ules over that ring. It hap­pens that the ring of in­te­gers mod 2 is what we want to use. A sim­plex is, topolog­i­cally, the same thing as a ball, and its bound­ary the same thing as a sphere.)

OK. So, first of all sup­pose not only that the num­ber of good sim­plices isn’t odd, but that it’s ac­tu­ally zero. Then f maps the whole of our sim­plex to its bound­ary. Let’s also con­sider the rather bor­ing map g from the bound­ary to the whole sim­plex that just leaves ev­ery point where it is. Now, if the thing we’re try­ing to prove is true in lower di­men­sions then in par­tic­u­lar the map gf—start on the bound­ary of the sim­plex, stay where you are us­ing g, and then map to the bound­ary of the sim­plex again us­ing f—has an image that, so to speak, cov­ers each bound­ary face of the sim­plex an odd num­ber of times. This guaran­tees—sorry, I’m elid­ing some de­tails here—that (gf)* (from the cyclic group of or­der 2 to the cyclic group of or­der 2) doesn’t map ev­ery­thing to the iden­tity. But that’s im­pos­si­ble, be­cause (gf)*=g*f* and the map f* maps to Hn(whole sim­plex) which is the triv­ial group.

Un­for­tu­nately, what we ac­tu­ally need to as­sume in or­der to prove this thing by con­tra­dic­tion is some­thing weaker: merely that the num­ber of good sim­plices is even. We can ba­si­cally do the same thing, be­cause ho­mol­ogy mod 2 “can’t see” things that hap­pen an even num­ber of times, but to see that we need to look a bit fur­ther into how ho­mol­ogy works. I’m not go­ing to lay it all out here, but the idea is that to build the Hd(X) we be­gin with a space of things called “chains” which are like lin­ear com­bi­na­tions (in this case over the field with two el­e­ments) of bits of X, we define a “bound­ary” op­er­a­tor which takes com­bi­na­tions of d-di­men­sional bits of X and turns them into com­bi­na­tions of (d-1)-di­men­sional bits in such a way that the bound­ary of the bound­ary of any­thing is always zero, and then we define Hd(x) as a quo­tient ob­ject: (d-di­men­sional things with zero bound­ary) /​ (bound­aries of d+1-di­men­sional things). Then the way we go from f (a map of topolog­i­cal spaces) to f* (a ho­mo­mor­phism of ho­mol­ogy groups) is that f ex­tends in a nat­u­ral way to a map be­tween chains, and then it turns out that this map in­ter­acts with the bound­ary op­er­a­tor in the “right” way for this to yield a map be­tween ho­mol­ogy groups. And (get­ting, fi­nally, to the point) if in our situ­a­tion the num­ber of good sim­plices is even, then this means that the map of chains cor­re­spond­ing to f sends any­thing in n di­men­sions to zero (es­sen­tially be­cause it means that the in­te­rior of the sim­plex gets cov­ered an even num­ber of times and when work­ing mod 2, even num­bers are zero), which means that we can think of f* as map­ping not to the ho­mol­ogy groups of the whole sim­plex but to those of its bound­ary—and then the ar­gu­ment above goes through the same as be­fore.

I apol­o­gize for the hand­wav­ing above. (Speci­fi­cally, the sen­tence be­gin­ning “This guaran­tees”.) If you’re fa­mil­iar with this stuff, it will be ap­par­ent how to fill in the de­tails. If not, try­ing to fill them in will only add to the pain of what’s already too long a com­ment :-).

This is clearly much too much ma­chin­ery to use here. I sus­pect that if we took the ar­gu­ment above, figured out ex­actly what bits of ma­chin­ery it uses, and then op­ti­mized ruth­lessly we might end up with a neat purely-com­bi­na­to­rial proof, but I re­gret that I am too lazy to try right now.

• Rough ap­proach for qu 6:

Join the cen­ter to each of the cor­ners and color each seg­ment a differ­ent color and ar­bi­trar­ily col­or­ing each am­bigu­ous point. Ra­di­ally ex­tend the col­ored sec­tions to in­finity.

To prove f(x) has a fixed point con­sider g(x) = f(x) - x which can take val­ues out­side of the tri­an­gle. To find a fixed point, we sim­ply need to show that g(x) will map at least one point to the cen­ter. It is easy to prove that each cor­ner will map to the color op­po­site and each edge can only map to points of a differ­ent color (un­less it passes through the cen­ter, in which case we would have ob­tained out proof). At this point the prob­lem re­duces to 5 as­sum­ing that we con­struct a big enough cir­cle.

• My solu­tion for #3:

Define by . We know that is con­tin­u­ous be­cause and the iden­tity map both are, and by the limit laws. Ap­ply­ing the in­ter­me­di­ate value the­o­rem (prob­lem #2) we see that there ex­ists such that . But this means , so we are done.

Coun­terex­am­ple for the open in­ter­val: con­sider defined by . First, we can ver­ify that if then , so in­deed maps to . To see that there is no fixed point, note that the only solu­tion to in is , which is not in . (We can also view this graph­i­cally by plot­ting both and and check­ing that they do not in­ter­sect in .)

• EDIT: I’ve got an­other fram­ing that I thought would be more use­ful for later prob­lems, but I was wrong. I still think there is some value in un­der­stand­ing this proof as well.

In par­tic­u­lar, look at this di­a­gram on Wikipe­dia. It would be bet­ter if the whole up­per tri­an­gle was blue and the whole lower tri­an­gle were red in­stead of just one side (you can ar­bi­trar­ily de­cide whether to paint the rest of the di­ag­o­nal blue or red). If x=0 and x=1 aren’t fixed points, then they must be blue and red re­spec­tively. If we split [0,1] into n com­po­nents of size 1/​n, then we can see where f(x) maps each such com­po­nent to and form a line of col­ored points as in q1. Prov­ing this us­ing Sperner’s Lemma is then es­sen­tially the same as qu2.

• Yeah, I did the same thing :)

Put­ting it right af­ter #2 was highly sug­ges­tive—I won­der if this means there’s some very differ­ent route I would have thought of in­stead, ab­sent the fram­ing.

• I’m late, but I’m quite proud of this proof for #4:

Call the large tri­an­gle a graph and the tri­an­gles sim­ply tri­an­gles. First, note that for any size, there is a graph where the top node is col­ored red, the re­main­ing nodes on the right di­ag­o­nal are col­ored green, and all nodes not on the right di­ag­o­nal are col­ored blue. This graph meets the con­di­tions, and has ex­actly one trichro­matic tri­an­gle, namely the one at the top (no other tri­an­gle con­tains a red node). It is triv­ial to see that this graph can be changed into an ar­bi­trary graph by re-col­or­ing finitely many nodes. This will af­fect up to six tri­an­gles; we say that a tri­an­gle has changed iff it was trichro­matic be­fore the re­col­or­ing but not af­ter, or vice versa, and we shall show that re-col­or­ing any node leads to an even num­ber of tri­an­gles be­ing changed. This proves that the num­ber of trichro­matic tri­an­gles never stops be­ing odd.

La­bel the three col­ors , and . Let be the node be­ing re­col­ored, wlog from to . Sup­pose first that has six neigh­bors. It is easy to see that a tri­an­gle be­tween and two neigh­bors has changed if and only if one of the neigh­bors has color and the other has color or . Thus, we must show that the num­ber of such tri­an­gles is even. If all neigh­bors have color , or if none of them do, then no tri­an­gles have changed. If ex­actly one node has color , then the two ad­ja­cent tri­an­gles have changed. Other­wise, let and de­note two differ­ent neigh­bors of color . There are two paths us­ing only neigh­bors of be­tween and . Both start and end at a node of color . By the 1-D Sperner Lemma (as­sum­ing the more gen­eral re­sult), it fol­lows that both paths have an even num­ber of edges be­tween nodes of color and ; these cor­re­spond to the tri­an­gles that have changed.

If is a node on one of the graph’s bound­aries chang­ing color from to , it has ex­actly 4 neigh­bors and three ad­ja­cent tri­an­gles. The two neigh­bors that are also on the bound­ary can­not have color , so ei­ther none, one, or both of the ones that aren’t do. If it’s none, no tri­an­gle has changed; if it’s one, the two neigh­bor­ing tri­an­gles have changed; and if it’s both, then the two tri­an­gles with two nodes on the graph’s bound­ary have changed.

• Some pre­limi­nary thoughts on q9:

As Jes­si­cata pointed out, in 3-di­men­sions or higher, our n-hedra don’t split up as nicely as in the 2d case.

That isn’t the only is­sue: many of the sur­faces of con­nected blocks may not cor­re­spond to the type of 2d grid that we just proved this re­sult for and it doesn’t seem triv­ial to figure out how to char­ac­ter­ise what kind of grids we need to ex­tend our re­sult too (it will be even worse in higher di­men­sions)

I’ve found two re­sults: firstly that if you re­move a tri­an­gu­lar face and re­place it with three oth­ers (imag­ine al­low­ing the sur­face to jut out of the page), then the trichro­matic par­ity will be pre­served. Se­condly, that we can re­place two tri­an­gle with four triangles

Given what I’ve dis­cussed above, I’d be keen for a hint as learn­ing enough ge­om­e­try to make progress on this prob­lem would seem to be tak­ing me pretty far afield from maths use­ful for ai-risk.

• Here’s the rough idea for 5 (not a full-proof)

The bot­tom edge must stick in the blue and green sec­tions mean­ing that if we were to di­vide the edge in n and see where these points map to, we would find that it would be blue or green and similarly the other edges would match the limi­ta­tions in q4. If we look at the right cor­ner, we see that the bot­tom edge maps to green or blue and the right edge maps to green or red, so the bot­tom cor­ner must be in green. Similarly the other cor­ners match the re­quire­ments of q4.

This lets us find a smaller trichro­matic tri­an­gle. We can re­peat this pro­cess an ar­bi­trary num­ber of times. Con­sider the range of pos­si­ble x and y co-or­di­nates of el­e­ments in these tri­an­gles. Each time this will re­duce by a par­tic­u­lar fac­tor, so we can see that the range of each co-or­di­nate will ap­proach 0. I’ll leave it to the reader to show that this means that these ranges con­verge to a point. I’ll also leave it to the reader to show that each trichro­matic sub-tri­an­gle must con­tain the cen­ter (you may want to look up wind­ing num­bers).

• I’ve re­al­ised that you’ve gotta be care­ful with this method be­cause when you find a trichro­matic sub­tri­an­gle of the origi­nal, it won’t nec­es­sar­ily have the prop­erty of only hav­ing points of two colours along the edges, and so may not in fact con­tain a point that maps to the cen­tre.

This isn’t a prob­lem if we just in­crease the num­ber n by which we di­vide the whole tri­an­gle in­stead of re­cur­sively di­vid­ing sub­tri­an­gles. Un­for­tu­nately now we’re not re­duc­ing the range of co-ords where this fixed point must be, only find­ing a triad of ar­bi­trar­ily close points that map to a tri­an­gle sur­round­ing the cen­tre. You can, for ex­am­ple, take the cen­tre point of the first of these tri­an­gles (with some method of num­ber­ing to make the func­tion definite) for each value of as a se­quence in . This must have a con­ver­gent se­quence which should con­verge to a point that maps to the cen­tre but I can’t prove that last stage.

• Here’s a solu­tion to 4:

We will first prove a lemma that all con­nected groups of green blocks that are com­pletely sur­rounded by red or blue blocks will pro­duce an even num­ber of trichro­matic tri­an­gles. We will then aug­ment the tri­an­gle by adding an ex­tra blue row on the bot­tom and an ex­tra red side on the right such that we now have would what be a tri­an­gle if it weren’t miss­ing the bot­tom right cor­ner. This will mean that all green blocks will now be sur­rounded so we’ll have an even num­ber of trichro­matic tri­an­gles, but we have added ex­actly one ad­di­tional such tri­an­gle, so that the origi­nal has an odd num­ber.

------

Proof of Lemma:

A triv­ial var­i­ant of 1-d Sperner’s Lemma is that if we start and finish on the same colour, we get an even num­ber of bichro­matic edges. For any block that is com­pletely sur­rounded by red and blue blocks, we ap­ply this var­i­ant to show that there is an even num­ber of bichro­matic edges on the out­side that then trans­lates to an even num­ber of trichro­matic tri­an­gles.

EDIT: Ac­tu­ally, there is one case we can run into which is tricky and that is some­thing like:

R R R R R

R G G G R

R G R B R

R G G G R

R R R R R R

To see how to solve this case, read how to solve tricky in­te­rior cases be­low.

END EDIT

Thick in­te­rior blocks work similarly, but we can run into weird sce­nar­ios such as a blue and a red sur­round­ing by green block:

g g g

g b r g

g g g

We might also run into some­thing like this (ie. a three-spoked shape that is blue at the cen­ter and red on the sides sur­rounded by green).

g g g

g r g g

g b r g

g r g g

g g g

For these weird shapes we can still trace a path around this in­te­rior sec­tion, we just in­clude go­ing both down and up a spoke in our path (thanks Hoagy!). So the in­te­rior sec­tions are also even.

• Strate­gies that I’ve found helpful:

If some­thing doesn’t seem tractable, try flip­ping be­tween alge­braic and ge­o­met­ric in­ter­pre­ta­tions of a prob­lem. Prob­lems 1 and 3 fell to this ap­proach.

Spe­cific solu­tions (or sug­ges­tive hand­wav­ing):

Prob­lem 1:

I thought of it like par­ity—go­ing left to right, each unichro­matic edge doesn’t change the color, while each bichro­matic edge does. So to have an over­all change, we need ei­ther 1 bichro­matic edge, or 3 (1 and 2 that can­cel), or 5 (1 and 4 that can­cel)...

Prob­lem 2:

I couldn’t un­der­stand this one at first. After check­ing Wikipe­dia, I think that refers to the space that each point in the se­quence lies within. An ex­am­ple of a finite se­quence in would then be

Prob­lem 3:

Con­sider the unit square. We need to draw one con­tin­u­ous line, go­ing from left to right, that cov­ers the en­tire ver­ti­cal ex­tent of the square. No mat­ter how you do that, you need to cross the di­ag­o­nal line from the bot­tom left to the top right.

Why? Be­cause you need to touch the top and the bot­tom edges. You can’t do that at the bot­tom-left or top-right cor­ners, since then you’d touch the di­ag­o­nal line. But then the point where you touch the top edge is en­tirely within the top tri­an­gle, and it can­not touch the bot­tom edge with­out en­ter­ing the bot­tom tri­an­gle. Switch­ing be­tween tri­an­gles is iden­ti­cal to cross­ing the di­ag­o­nal line.

As for why this isn’t true if the set is open rather than closed: if we ex­clude the edges from our con­sid­er­a­tion of “does it in­ter­sect the di­ag­o­nal”, then it’s fairly triv­ial to con­struct a curve that stays in­side one tri­an­gle and has a codomain of (0,1). should work.

• #8 ac­tu­ally comes up in physics:

in the field of non­lin­ear dy­nam­ics (pretty pic­ture, ac­tual wikipe­dia). The fact that con­tin­u­ous changes in func­tions can lead to sur­pris­ing changes in fixed points (speci­fi­cally sta­ble at­trac­tors) is pretty darn im­por­tant to un­der­stand­ing e.g. phase tran­si­tions!

• Does this work for #7? (and ques­tion) (Spoilers for #6):

I did #6 us­ing 2D Sperner’s lemma and closede­ness. Imag­ine the the des­ti­na­tion points are col­ored [as in #5, which was a nice hint] by where they are rel­a­tive to their source points—split the pos­si­ble differ­ence vec­tors into a col­ored cir­cle as in #5 [pick the cen­ter to be a fourth color so you can no­tice if you ever sam­ple a fixed point di­rectly, but if fixed points are rare this shouldn’t mat­ter], and take sam­ples to make it look like 2d Sperner’s lemma, in which there must be at least one in­te­rior tri-col­ored patch. Define a limit of zoom­ing in that moves you to­wards the tri-col­ored patch, ap­ply closed­ness to say the cen­ter (fixed) point is in­cluded, much like how we were en­couraged to do #2 with 1D Sperner’s lemma.

To do #7, it seems like you just need to show that there’s a con­tin­u­ous bi­jec­tion that pre­serves whether a point is in­te­rior or on the edge, from any con­vex com­pact sub­set of R^2 to any other. And there is in­deed a recipe to do this—it’s like you imag­ine sweep­ing a line across the two shapes, at rates such that they finish in equal time. Ap­ply a 1D trans­for­ma­tion (af­fine will do) at each point in time to make the two cross sec­tions match up and there you are. This uses the prop­erty of con­vex­ity, even though it seems like you should be able to strengthen this the­o­rem to work for sim­ply con­nected com­pact sub­sets (if not—why not?).

EDIT: (It turns out that I think you can con­struct patholog­i­cal shapes with un­countable num­bers of edges for which a sim­ple lin­ear sweep fails no mat­ter the an­gle, be­cause you’re not al­lowed to sweep over an edge of one shape while sweep­ing over a ver­tex of the other. But if we al­low the an­gle to vary slightly with para­met­ric ‘time’, I don’t think there’s any pos­si­ble coun­terex­am­ple, be­cause you can always find a way to start and end at a ver­tex.)

Then once you’ve mapped your sub­set to a tri­an­gle, you use #6. But.

This doesn’t use the hint! And the hints have been so good and ed­u­ca­tional ev­ery­where I’ve used them. So what am I miss­ing about the hint?

• An at­tempt at prob­lem #1; seems like there must be a shorter proof.

The proof idea is “If I flip a light switch an even num­ber of times, then it must be in the same state that I found it in when I’m finished switch­ing.”

The­o­rem. Let e a path graph on er­tices with a ver­tex olor­ing uch that if hen Let s bichro­matic Then s odd.

Proof. By the defi­ni­tion of a path graph, there ex­ists a se­quence ndex­ing An edge s bichro­matic iff A sub­graph f s a state iff its ter­mi­nal ver­tices are each in­ci­dent with ex­actly one bichro­matic edge or equal to a ter­mi­nal ver­tex of The color of a state is the color of its ver­tices. There ex­ists a sub­se­quence of on­tain­ing the least term of each state; the in­dex of a state is equal to the in­dex of its least term in this sub­se­quence.

Note that none of the states with even in­dexes are the same color as any of the states with odd in­dexes; hence all of the states with even in­dexes are the same color, and all of the states with odd in­dexes are the same color.

For each state there ex­ists a sub­se­quence of or­re­spond­ing to the ver­tices of and the least term of each sub­se­quence is ei­ther r some hat is the great­est term in a bichro­matic edge. Thus the num­ber of states in

By con­tra­dic­tion, sup­pose that s even. Then the num­ber of states is odd, and the first and last states are the same color, so the ter­mi­nal ver­tices of re the same color, con­trary to our as­sump­tion that they are differ­ent col­ors. Thus ust be odd.

:::

• Turn­ing each node but the last blue from left to right con­serves the par­ity of the bichro­matic edge count at each step un­til it is still odd at the end.

• I’m stuck part-way through on #4 - I as­sume there is a way to do this with­out the ex­haus­tive search I’m run­ning into need­ing.

I’m go­ing to try (nested) in­duc­tion. Define tri­an­gles by side size, mea­sured in nodes.

In­duc­tion base step: For n=2, there must be ex­actly one trichro­matic edge.

In­duc­tion step: If there are an odd num­ber of tri-chro­matic edges for all tri­an­gles n=x, we must show that this im­plies the same for n=x+1.

We cre­ate all pos­si­ble new tri­an­gles by adding x+1 nodes on one of the sides, then al­low any of the pre­vi­ous x nodes on that side to change. Without loss of gen­er­al­ity, as­sume we add x+1 edges to the bot­tom (non-red) side. Th­ese must be green or blue. The pre­vi­ous layer can now change any num­ber of node-col­ors. We now must prove this by in­duc­tion on color changes of nodes in the sec­ond-to-bot­tom layer to be red. (If they flip color oth­er­wise, it is cov­ered by a differ­ent base case.)

First, base step, as­sume no nodes change color. Be­cause the pre­vi­ous tri­an­gle had an odd num­ber of trichro­matic edges, and the new edge is only green+blue, no new trichro­matic edges were cre­ated.

In­duc­tion step: There is an x+1 tri­an­gle with an odd num­ber of trichro­matic ver­tices, and one node in the sec­ond-to-bot­tom layer changes to red. This can only cre­ate a new tri-cro­matic tri­an­gle in one of the six ad­ja­cent tri­an­gles. We split this into (lots of) cases, and han­dle them one at a time.

(Now I get into WAY too many cases. I started and did most of the edge-node case, but it’s a huge pain. Is there some other way to do this, pre­sum­ably us­ing some nifty graph the­ory I don’t know, or will I need to list these out? Or should I not be us­ing the nested in­duc­tion step?)

Poin­t­ers wel­come!

• You can use 1d-Sperner to deal with all the cases effec­tively.

• Here’s a messy way that at least doesn’t need too much ex­haus­tive search:

First let’s sep­a­rate all of the red nodes into groups so that within each group you can get to any other node in that group only pass­ing through red nodes, but not to red nodes in any other group.

Now, we trace out the paths that sur­round these groups—they im­me­di­ately look like the paths from Ques­tion 1 so this feels like a good start. More pre­cisely, we draw out the paths such that each ver­tex forms one side of a tri­an­gle that has a blue node at its op­po­site cor­ner. Note that you can have mul­ti­ple paths stem­ming from the same group if the group touches the side of the larger tri­an­gle, or if it has in­ter­nal holes.

Now we have this set of paths we can split them into three kinds. The first is loops, which arise when you have a group which never touches the edge of the larger tri­an­gle, or in­side ‘holes’ in large groups. Th­ese can be seen as a path start­ing and finish­ing at the same node. They there­fore have an even num­ber of b-g ver­tices. The sec­ond kind is those that be­gin at the edge of the large tri­an­gle and end at the same edge. Th­ese paths be­gin and end on the same colour and there­fore also have an even num­ber of b-g ver­tices. Fi­nally and most im­por­tantly there is a kind of path that goes from one edge to the other -in the case of the reds, the left edge to the right edge. This will hap­pen once with the group that in­cludes the top red node, and if any other group spans the larger tri­an­gle then it will gen­er­ate two more of these paths. Sperner’s lemma tells us that these will have an odd num­ber of b-g ver­tices and we know that there will be an odd num­ber of such paths, so this fi­nal type gen­er­ates an odd num­ber of to­tal b-g ver­tices.

By the way that we have defined these paths, the to­tal num­ber of r-g-b tri­an­gles is equal to the num­ber of g-b ver­tices on the paths in the set gen­er­ated above. This num­ber is the sum of an odd num­ber from the span­ning paths and a se­ries of even num­bers from the other paths, giv­ing an odd over­all num­ber of r-g-b ver­tices, prov­ing num­ber 4 (as long as I haven’t made an er­ror in cat­e­go­riz­ing the paths).

I hope this makes sense, let me know if it doesn’t or has er­rors :)

• I am hav­ing trou­ble figur­ing out why #2 needs /​ benefits from Sperner’s Lemma.

But I keep go­ing back to the proof that I’m com­fortable with, which de­pends on con­nect­ed­ness, so I’m clearly miss­ing an ob­vi­ous al­ter­na­tive proof that doesn’t need topol­ogy.

• I was able to get at least (I think) close to prov­ing 2 us­ing Sperner’s Lemma as fol­lows:

You can map the con­tin­u­ous func­tion f(x) to a path of the kind found in Ques­tion 1 of length n+1
by eval­u­at­ing f(x) at x=0, x=1 and n-1 equally spaced di­vi­sions be­tween these two points and set­ting a node as blue if f(x) < 0 else as green.

By Sperner’s Lemma there is an odd, and there­fore non-zero num­ber of b-g ver­tices. You can then take any b-g pair of nodes as the start­ing points for a new path and re­peat the pro­cess. After k iter­a­tions you have two val­ues of x—only one where f(x) is be­low zero—that are 1/​(n^k) away from each other. We thus can find ar­bi­trar­ily close points that strad­dle zero. By tak­ing the se­quence f(x) of ini­tial nodes x we get a se­quence that, by B-W, has a sub-se­quence which con­verges to zero. By con­ti­nu­ity we have proved the ex­is­tence of an x such that f(x)=0.

We can be sure that the sub-se­quence does in fact con­verge to zero, rather than any other value be­cause if it con­verges to any num­ber |a|>0, the gra­di­ent of f(x) would have to be ar­bi­trar­ily high to dip back be­low/​above 0 for a value of x ar­bi­trar­ily close by and there­fore would not be a con­tin­u­ous func­tion.

Com­ments to tighten up/​poke holes in the above ap­pre­ci­ated :)

• I’m hav­ing trou­ble un­der­stand­ing why we can’t just fix in your proof. Then at each iter­a­tion we bi­sect the in­ter­val, so we wouldn’t be us­ing the “full power” of the 1-D Sperner’s lemma (we would just be us­ing some­thing close to the base case).

Also if we are only given that is con­tin­u­ous, does it make sense to talk about the gra­di­ent?

• “I’m hav­ing trou­ble un­der­stand­ing why we can’t just fix n=2 in your proof. Then at each iter­a­tion we bi­sect the in­ter­val, so we wouldn’t be us­ing the “full power” of the 1-D Sperner’s lemma (we would just be us­ing some­thing close to the base case).”—You’re right, you can prove this with­out us­ing the full power of Sperner’s lemma. I think it be­comes more use­ful for the multi-di­men­sional case.

• Yeah agreed, in fact I don’t think you even need to con­tinu­ally bi­sect, you can just in­crease n in­definitely. Iter­at­ing be­comes more dan­ger­ous as you move to higher di­men­sions be­cause an n di­men­sional sim­plex with n+1 colours that has been coloured ac­cord­ing to analo­gous rules doesn’t nec­es­sar­ily con­tain the point that maps to zero.

On the sec­ond point, yes I’d been as­sum­ing that a bounded func­tion had a bounded gra­di­ent, which cer­tainly isn’t true for say sin(x^2), the fi­nal step needs more work, I like the way you did it in the proof be­low.

• I hit that stum­bling block as well. I hand­waved it by say­ing “con­tinue iter­at­ing un­til you have and such that , , and f has no lo­cal max­ima or lo­cal min­ima on the open in­ter­val ”, but that doesn’t work for the Weier­strass func­tion, which will (I be­lieve) never meet that crite­rion.

• Here is my at­tempt, based on Hoagy’s proof.

Let be an in­te­ger. We are given that and . Now con­sider the points in the in­ter­val . By 1-D Sperner’s lemma, there are an odd num­ber of such that and (i.e. an odd num­ber of “seg­ments” that be­gin be­low zero and end up above zero). In par­tic­u­lar, is an even num­ber, so there must be at least one such num­ber . Choose the small­est and call this num­ber .

Now con­sider the se­quence . Since this se­quence takes val­ues in , it is bounded, and by the Bolzano–Weier­strass the­o­rem there must be some sub­se­quence that con­verges to some num­ber .

Con­sider the se­quences and . We have for each . By the limit laws, as . Since is con­tin­u­ous, we have and as . Thus and , show­ing that , as de­sired.

• Ex 1

Let and . Given an edge , let de­note the map that maps the color of the left to that of the right node. Given a , let . Let de­note the color blue and the color green. Let be 1 if edge is bichro­matic, and 0 oth­er­wise. Then we need to show that . We’ll show , which is a stri­clty stronger state­ment than the con­tra­pos­i­tive.

For , the LHS is equiv­a­lent to , and in­deed equals if is bichro­matic, and oth­er­wise. Now let and let it be true for . Sup­pose . Then, if , that means , so that , and if , then , so that . Now sup­pose . If , then , so that , and if , then , so that . This proves the lemma by in­duc­tion.

Ex 2

Or­di­nar­ily I’d proof by con­tra­dic­tion, us­ing se­quences, that can nei­ther be greater nor smaller than 0. I didn’t man­age a short way to do it us­ing the two lem­mas, but here’s a long way.

Set . Given , let be a path graph of ver­tices , where . If for any and we have , then we’re done, so as­sume we don’t. Define to be 1 if and have s differ­ent sign, and 0 oth­er­wise. Sperner’s Lemma says that the num­ber of edges with are odd; in par­tic­u­lar, there’s at least one. Let the first one be de­noted , then set .

Now con­sider the se­quence . It’s bounded be­cause . Us­ing the Bolzano-Weier­strass the­o­rem, let be a con­ver­gent sub­se­quence. Since for all , we have . On the other hand, if , then, us­ing con­ti­nu­ity of , we find a num­ber such that . Choose and such that , then for all , so that and then for all , so that , a con­tra­dic­tion.

Ex 3

Given such a func­tion , let be defined by . We have . If ei­ther in­equal­ity isn’t strict, we’re done. Other­wise, . Tak­ing for granted that the in­ter­me­di­ate value the­o­rem gen­er­al­izes to this case, find a root of , then .

Is there some­thing I’m miss­ing? It seems to me that for all .

• is defined just for one par­tic­u­lar graph. It’s the first edge in that graph such that . (So it could have been called ). Then for the next graph, it’s a differ­ent . Ba­si­cally, looks at where the first graph skips over the zero mark, then picks the last ver­tex be­fore that point, then looks at the next larger graph, and if that graph skips later, it up­dates to the last ver­tex be­fore that point in that graph, etc. I think the rea­son I didn’t add in­dices to was just that there ar ealready the with two in­dices, but I see how it can be con­fus­ing since hav­ing no in­dex makes it sound like it’s the same value all through­out.

• Ex 5 (fixed ver­sion)

Let de­note the tri­an­gle. For each , con­struct a 2-d sim­plex with nodes in , where the color of a point cor­re­sponds to the place in the disk that car­ries that point to, then choose to be a point within a trichro­matic tri­an­gle in the graph. Then is a bounded se­quence hav­ing a limit point . Let be the cen­ter of the disc; sup­pose that . Then there is at least one re­gion of the disc that doesn’t touch. Let be the dis­tance to the fur­thest side, that is, let . Since the sides are closed re­gions, we have . Us­ing con­ti­nu­ity of , choose small enough such that . Then choose large enough so that (1) all tri­an­gles in have di­ame­ter less than and (2) . Then, given any other point in the tri­an­gle around in , we have that , so that . This proves that the tri­an­gle in does not map points to all three sides of the disc, con­tra­dict­ing the fact that it is trichro­matic.

Ex 6

(This is way eas­ier to demon­strate in a pic­ture in a way that leaves no doubt that it works than it is to write down, but I tried to do it any­way con­sid­er­ing that to be part of the difficulty.)

(As­sume the tri­an­gle is equilat­eral.) Imbed into such that , , . Let be con­tin­u­ous. Then given by is also con­tin­u­ous. If then . Let be the cir­cle with ra­dius 2 around ; then be­cause (it is in fact con­tained in the cir­cle with ra­dius 1, but the size of the cir­cle is in­con­se­quen­tial). We will use ex­er­cise 5 to show that maps a point to the cen­ter, which is , from which the de­sired re­sult fol­lows. For this, we shall show that it has the needed prop­er­ties, with the mod­ifi­ca­tion that points on any side may map pre­cisely into the cen­ter. It’s ob­vi­ous that weak­en­ing the re­quire­ment in this way pre­serves the re­sult.

Ro­tate the disk so that the red shape is on top. In po­lar co­or­di­nates, the green area now con­tains all points with an­gles be­tween and , the blue area con­tains those be­tween and , and the red area those be­tween and and those be­tween and . We will show that does not in­ter­sect the red area, ex­cept at the ori­gin. First, note that we have

Since both and are con­vex com­bi­na­tions of finitely many points, it suffices to check all com­bi­na­tions that re­sult by tak­ing a cor­ner from each. This means we need to check the points

and and and and and .

Which are eas­ily com­puted to be

and and and and and

Two of those are pre­cisely the ori­gin, the other four have an­gles and and and . In­deed, they are all be­tween and .

Now one needs to do the same for the sets and , but it goes through analo­gously.

• I am sorry be­cause I can­not figure out how to hide big for­mu­las in a spoiler. Also the spoiler fea­ture is some­what bro­ken so it adds weird tabs around for­mu­las.

#1:

Let’s count the num­ber of blue edge ends. Each blue point in­side the seg­ment is the end of two blue edges, and the left­most blue ver­tex is the end of one. There­fore, their to­tal num­ber is odd. On the other hand, each bichro­matic edge pro­duces one blue edge end, and each unichro­matic edge pro­duces an odd num­ber—zero or two—of blue edge ends. There­fore, an odd num­ber of edges are bichro­matic.

#2:

Sup­pose . If then and, since f is con­tin­u­ous, f stays pos­i­tive in some neigh­bor­hood of x, and then x is not the in­fi­mum. There­fore, f(x) = 0.

#3:

Con­sider the func­tion . Since and by ex­er­cise 2, there should be a point where g(x) = 0.

#8.

Con­sider the fam­ily of func­tions:

For t < 0.5, the only fixed point is of is 1; for t > 0.5, the only fixed point is 0.

#9.

Lemma:

Sup­pose a k-di­men­sional sim­plex is sub­di­vided into smaller k-di­men­sional sim­plices and all ver­tices are col­ored into k+1 col­ors so that there are no ver­tices of color i on the i-th edge of the big sim­plex. Then there are an odd num­ber of sub­di­vi­sion sim­plices whose ver­tices are col­ored in k+1 differ­ent col­ors.

Proof:

In­duc­tion by k. Base k=1 proved in ex­er­cise 1.

In­duc­tion step: sup­posed the lemma is proved for k-1, let’s prove it for k.

Let us count the num­ber of tu­ples (X, Y) where X is a k-1-di­men­sional sim­plex col­ored in col­ors 0, 1, …, k-1,

Y is a k-di­men­sional sub­di­vi­sion sim­plex, and X is on the bound­ary of Y. Each prop­erly col­ored sim­plex X in­side the big sim­plex pro­duces two tu­ples, and each sim­plex on the bound­ary pro­duces one tu­ple. X can only be on the k-th edge of the big sim­plex, and by the in­duc­tional as­sump­tion, there are an odd num­ber of sim­plices X there. So, the to­tal num­ber of tu­ples is odd. On the other hand, each k-di­men­sional sim­plex Y can be a part of ei­ther:

0 tu­ples;

1 tu­ple if all his ver­tices are differ­ent;

2 tu­ples if has ver­tices of col­ors 0,1,...,k-1 but not all his ver­tices are differ­ent.

There­fore, a num­ber of k-sim­plices Y with all differ­ent ver­tices must be odd.

#4

Fol­lows from 9

#5

Sup­pose that cen­ter is not in the image of the tri­an­gle. Let us call a set of points bichro­matic if it doesn’t have points of all three col­ors. We color each point in the tri­an­gle in the same color as its image. Then ev­ery point in the image has an open bichro­matic neigh­bor­hood. Since the map is con­tin­u­ous, the preimage of this neigh­bor­hood is also open. So, around ev­ery point in the tri­an­gle there can be drawn an open bichro­matic ball of ra­dius r. Th­ese balls are an open cover of the tri­an­gle, let us choose a finite sub­cover out of them. Sup­pose s the min­i­mum ra­dius in this sub­cover. Split the tri­an­gle into sub­tri­an­gles so that the di­ame­ter of each tri­an­gle is smaller than By Sperner’s lemma, there is a trichro­matic tri­an­gle, but since its di­ame­ter is smaller than it lies com­pletely in­side one of the bichro­matic balls. Con­tra­dic­tion.

#10

First, I am go­ing to prove that a func­tion from a unit ball o it­self has a fixed point, then that any com­pact con­vex sub­set of s home­o­mor­phic to a ball.

Sup­pose that as no fixed point, n>1 (case n=1 was proved in ex­er­cise 3). Then I can build a re­trac­tion from nto its bound­ary

send x to the first in­ter­sec­tion of the ray (f(x), x) with Let us prove that such a rec­trac­tion can­not ex­ist. Sup­pose that such a rec­trac­tion ex­ists. Denote the in­clu­sion map. Then nd the in­duced ho­mol­ogy group ho­mor­phism ust also be iden­tity:

But this is im­pos­si­ble be­cause and

Now let us prove that any com­pact con­vex sub­set X of s home­o­mor­phic to a ball. Let us se­lect a max­i­mum set of af­finely in­de­pen­dent points in X. They form some k-di­men­sional sim­plex, all X lies in the af­fine space spanned by this sim­plex, and all the in­te­rior of this sim­plex be­longs to X, be­cause X is con­vex. I’ll take a ball f ra­dius side this sim­plex and build a home­o­mor­phism be­tween X and . Tak­ing the cen­ter of the ball as the cen­ter of co­or­di­nates, define

where s the dis­tance to the farthest point of X in the di­rec­tion, if , 0 if

Let us prove that f and its in­verse are con­tin­u­ous. Since X is com­pact, it is bounded, so there is a such that It fol­lows that f and its in­verse are con­tin­u­ous in zero: if if

Now let us prove that func­tions are con­tin­u­ous in all other points. It is suffi­cient to prove that r(x) is the con­tin­u­ous on the unit sphere. (Since com­po­si­tion and product of con­tin­u­ous func­tions is con­tin­u­ous, di­vi­sion by bounded from be­low (by d) con­tin­u­ous func­tion r is con­tin­u­ous, ||x|| is a con­tin­u­ous func­tion).

Since X is con­vex, the tan­gent cone from any point of X to lies in X. So if we take a point at the dis­tance from the cen­ter, draw a tan­gent cone, and go down its bound­ary, we get the steep­est pos­si­ble rate of change of r(x) with re­spect to x. There­fore, r is con­tin­u­ous.

#6, #7: fol­low from #10.

#11:

Sup­pose f has no fixed point. Dis­tance d(a, B) is a con­tin­u­ous func­tion of a, and a con­tin­u­ous func­tion reaches its min­i­mum on a com­pact. TxT and the graph of f are non­iter­sect­ing com­pact sets, there­fore the Haus­dorff dis­tance be­tween them is pos­i­tive. It is easy to see that Haus­dorff met­ric is in­deed a met­ric, i.e. that a tri­an­gle in­equal­ity holds for it. So if we take any con­tin­u­ous func­tion g at a dis­tance less than from f, its Haus­dorff dis­tance to TxT will be pos­i­tive, so it can have no fixed points.

#13:

Sup­pose is a Kaku­tani func­tion. We already know that any com­pact con­vex sub­set of s home­o­mor­phic to a sim­plex. Denote he home­o­mor­phism be­tween a sim­plex T and S.

Denote the k-th bar­ithen­tric sub­di­vi­sion of T. For each choose an el­e­ment

Define where are the bari­cen­tric co­or­di­nates of point n its sub­di­vi­sion sim­plex. Func­tion s con­tin­u­ous, and, since S is con­vex, the image of lies in S.

By the Brouwer fixed point the­o­rem, as a fixed point. Since S is com­pact, from the in­finite se­quence of fixed points of e can choose a con­ver­gent sub­se­quence.

Sup­pose s this sub­se­quence, lies in the sim­plex and has bari­cen­tric co­or­di­nates . Then and so

(1).

Since sim­plices go down in di­ame­ter, as Each s a bounded se­quence, so we can, se­quen­tially, choose a con­ver­gent sub­se­quence out of each of them, so we can as­sume that Similarly, we can choose a con­ver­gent sub­se­quence out of so we as­sume The se­quence be­longs to the graph of h and con­verges to the point Since the graph is closed, must be­long to the image of Since for ev­ery k, ince the image is con­vex, lso be­longs to the image of On the other hand, as we re­mem­ber, since equal­ity (1) held for ev­ery k, it also holds in the limit: . Hence, So, is the fixed point of h.

• I just tried to fix all the things in your com­ment. You’re right, weird stuff was hap­pen­ing :-)

• Thank you!