6.2. LABELING VERTICES 159

6.2 Labeling VerticesNext is a way to label the vertices. Let p0, · · · , pn be the first n+ 1 prime numbers. Allvertices of a simplex S = [x0, · · · ,xn] having {xk−x0}n

k=1 independent will be labeledwith one of these primes. In particular, the vertex xk will be labeled as pk if the simplex is[x0, · · · ,xn]. The “value” of a simplex will be the product of its labels. Triangulate this S.

Consider a 1 simplex whose vertices are from the vertices of S, the original n simplex[xk1 ,xk2

], label xk1 as pk1 and xk2 as pk2 . Then label all other vertices of this triangulation

which occur on[xk1 ,xk2

]either pk1 or pk2 . Note that by independence of {xk−xr}k ̸=r ,

this cannot introduce an inconsistency because the segment cannot contain any other vertexof S. Then obviously there will be an odd number of simplices in this triangulation havingvalue pk1 pk2 , that is a pk1 at one end and a pk2 at the other. Next consider the 2 simplices[xk1 ,xk2 ,xk3

]where the xki are from S. Label all vertices of the triangulation which lie

on one of these 2 simplices which have not already been labeled as either pk1 , pk2 , or pk2 .Continue this way. This labels all vertices of the triangulation of S which have at least onecoordinate zero. For the vertices of the triangulation which have all coordinates positive,the interior points of S, label these at random from any of p0, ..., pn. (Essentially, this isthe same idea. The “interior” points are the new ones not already labeled.) The idea isto show that there is an odd number of n simplices with value ∏

ni=0 pi in the triangulation

and more generally, for each m simplex[xk1 , · · · ,xkm+1

],m ≤ n with the xki an original

vertex from S, there are an odd number of m simplices of the triangulation contained in[xk1 , · · · ,xkm+1

], having value pk1 · · · pkm+1 . It is clear that this is the case for all such 1

simplices. For convenience, call such simplices[xk1 , · · · ,xkm+1

]m dimensional faces of S.

An m simplex which is a subspace of this one will have the “correct” value if its value ispk1 · · · pkm+1 .

Suppose that the labeling has produced an odd number of simplices of the triangulationcontained in each m dimensional face of S which have the correct value. Take such an mdimensional face

[x j1 , . . . ,x jk+1

]. Consider Ŝ≡[x j1 , . . .x jk+1 ,x jk+2

]Then by induction, there is an odd number of k simplices on the sth face[

x j1 , . . . , x̂ js , · · · ,x jk+2

]having value ∏i ̸=s p ji . In particular, the face

[x j1 , . . . ,x jk+1 , x̂ jk+2

]has an odd number of

simplices with value ∏i≤k+1 p ji .No simplex in any other face of Ŝ can have this value by uniqueness of prime factoriza-

tion. Pick a simplex on the face[x j1 , . . . ,x jk+1 , x̂ jk+2

]which has correct value ∏i≤k+1 p ji

and cross this simplex into Ŝ. Continue crossing simplices having value ∏i≤k+1 p ji whichhave not been crossed till the process ends. It must end because there are an odd numberof these simplices having value ∏i≤k+1 p ji . If the process leads to the outside of Ŝ, thenone can always enter it again because there are an odd number of simplices with value∏i≤k+1 p ji available and you will have used up an even number. Note that in this process,if you have a simplex with one side labeled ∏i≤k+1 p ji , there is either one way in or outof this simplex or two depending on whether the remaining vertex is labeled p jk+2 . Whenthe process ends, the value of the simplex must be ∏

k+2i=1 p ji because it will have the addi-

tional label p jk+2 . Otherwise, there would be another route out of this, through the otherside labeled ∏i≤k+1 p ji . This identifies a simplex in the triangulation with value ∏

k+2i=1 p ji .