1. Synopsis
One of the major headaches of using complex numbers in olympiad geometry problems is dealing with square roots. In particular, it is nontrivial to express the incenter of a triangle inscribed in the unit circle in terms of its vertices.
The following lemma is the standard way to set up the arc midpoints of a triangle. It appears for example as part (a) of Lemma 6.23.
Theorem 1 (Arc midpoint setup for a triangle)
Let 
Suppose we view 
Theorem 1 is often used in combination with the following lemma, which lets one assign the incenter the coordinates 
Lemma 2 (The incenter is the orthocenter of opposite arc midpoints)
Let 
Unfortunately, the proof of Theorem 1 in my textbook is wrong, and I cannot find a proof online (though I hear that Lemmas in Olympiad Geometry has a proof). So in this post I will give a correct proof of Theorem 1, which will hopefully also explain the mysterious introduction of the minus signs in the theorem statement. In addition I will give a version of the theorem valid for quadrilaterals.
2. A Word of Warning
I should at once warn the reader that Theorem 1 is an existence result, and thus must be applied carefully.
To see why this matters, consider the following problem, which appeared as problem 1 of the 2016 JMO.
Example 3 (JMO 2016, by Zuming feng)
The isosceles triangle 
By experimenting with the diagram, it is not hard to guess that the correct fixed point is the midpoint of arc 
This is a mistake! If one applies Theorem 1 twice, then the choices of “square roots” of the common vertices 
In fact, I claim this is not a minor issue that one can work around. This is because the claim that the circumcircle of 
3. Proof of the theorem for triangles
Fix 
We pick an arbitrary choice for 
The main trick is to now consider the arc midpoint 
Lemma 4 (The isosceles trapezoid trick)
We have 
Thus, we have
Thus
as desired.
From this we can see why the minus signs are necessary.
, 
, 
instead of 4. A version for quadrilaterals
We now return to the setting of a convex quadrilateral 
Theorem 6 (
Let
- The opposite arc midpoints
,
, as before.
- The midpoint of arc
not including
.
- The midpoint of arc
not including
.
- The midpoint of arc
is
and the midpoint of arc
is
.
This setup is summarized in the following figure.
Note that unlike Theorem 1, the four arcs cut out by the sides of 
Proof: We select
On the other hand, the calculation of 
In other problems, the four vertices of the quadrilateral may play more symmetric roles and in that case it may be desirable to pick a setup in which the four vertices are labeled 
Corollary 7
Let 
- The midpoints of
,
cut out by the sides of
,
,
,
.
- The midpoints of
and
are
and
.
- The midpoints of
and
are
and
.
To test the newfound theorem, here is a cute easy application.
Example 8 (Japanese theorem for cyclic quadrilaterals)
In a cyclic quadrilateral 
, …, 
an 
-ascending permutation is a permutation on 
whose descent set is contained in 
. In other words the permutation ascends in blocks of length 
, …, 
for all 
.
denote the set of 
.
will be explained later.) In particular, 
if 
.
(but not in 
, since one can see an increasing length 
subsequence shaded). We would denote it 
.
and 
are in bijection with Young tableau of shape 
.
, this implies 
, which is the set of 
-avoiding permutations of length 
, is in bijection with the Catalan numbers; so is 
which is the set of 
and 
‘s. To simplify notation,
. Then 
denotes 
where
sets 
notation is my own invention, and did not exist when I originally started working on the problem. Indeed, all the results are restricted to the case where 
for each 
: Mei and Wang’s paper use the notation 
for any 
and 
, it would suffice to biject
and 
. Indeed, suppose 
is an increasing sequence of length 
. So 
had better be the largest element in the permutation: otherwise later in 
.
. Then there is a bijection
st element of the permutation (which must be largest one).
. The “easy case” I had found told me that I could take a set 
from it. So empirically, my intuition from this toy example told me that it would be easier to find bijections 
whee 
and 
, then we would be done.
. Then using a C++ computer program:
.
.
.
and 
permutation takes 
time, and there are 
or so permutations. But when 
, we have 
, which is a pretty big number. Unfortunately, my computer is not really that fast, and I didn’t really have the patience to implement the “correct” algorithms to bring the runtime down.
instead.
. My reasoning was that since I was only doing this for heuristic reasons, I could instead work with 
and probably not change much about the structure of the problem, while replacing 
, which would run 
times faster. This was okay since all I wanted to do was see how much changing the “middle” would disrupt the structure.
.
.
.
were equal. In other words, the outer blocks were preserved: the bijection
.
, 
. There is a bijection
st blocks.
. How could I figure out what it was?
and 
are order-isomorphic if 
if and only 
. Then order-isomorphism gives equivalence classes, and there is a canonical representative where the letters are 
; this is called a reduced word.
, 
and 
are order-isomorphic; the last is reduced.
changed to 
; then we would expect that in another situation we should have 
changing to 
. Indeed, we expect 
and the particular sets
which starts with 
is 
.
which starts with 
.
is changed to 
. Thus the empirical data shows that
, there is more than one.
and 
are both in 
and 
are both in in 
down to two values, but if you look at other places you might have different data on 
, we’ve matched the other.
and 
.
, and look at the permutations that start and end with those particular four elements. Record the reductions of 
and 
for all these permutations. We call these input words and output words, respectively. Each output word is a “candidate” of 
that appeared, take the intersection of all output words that appeared. This gives a bipartite graph 
, with input words being matched to their candidates.
is on the right half, then it always moves over.
if 
, or 
if no such index exists.
and 
also had the same cardinality. Huh.
seemed to only depend on the order of the 
. (This was interesting, because the 
elements in question could now have either longest increasing subsequence of length 
.
(of which there are 
) and
with two distinguished nodes 
).
.
):
, by David Cox (
, where 
. 
: by Fermat’s Christmas theorem, the primes 
(and 
) can all be written as the sum of two squares, while the primes 
cannot. For convenience, let us say that: 
be a quadratic form. We say it 
if there exists 
with 
. Moreover, 
is (properly) represented by 
. 
(and 
) then 
. 
and 
should clearly be considered the same. More generally, if we think of 
and 
is any automorphism of 
should be considered the same as 
and 
said to be 
. We have 
and so we say the equivalence is 
, and
. 
is defined as 
.
and 
(thus 
too) then 
for all 
. Such quadratic forms are called 
, and
if either 
or 
. 
we can consider the set 
; by the exercise, 
. This is called the 
, because we can take 
for 
and 
for 
. We call this form the 
, 
, with form 
.
, with form 
.
, with form 
.
, with form 
.
, with form 
. 
, with form 
.
, with form 
.
, with form 
.
, with form 
.
, with form 
.
, with form 
.
, with form 
.
, with form 
. 
. When 
, with 
forms 
and 
.
, with 
and 
.
, with 
and 
.
, with 
and 
.
, with 
and 
.
, with 
forms 
and 
. 
, with 
and 
.
, with 
and 
.
, with 
and 
.
, with 
forms 
, 
and 
. 
has 
, 
and 
.
has 
and 
.
has 
, 
and 
. 
, and observed that for odd primes 
be an odd prime. Then the following are equivalent: 
, i.e. 
. 
in an essential way! That is: if 
, we know 
and 
. Thus 
, since otherwise this would imply 
. Then 
.
for integers 
. Now 
. This is abuse of notation since I should technically write 
, but there is no harm done: one can check by quadratic reciprocity that if 
then 
. Thus our previous result becomes: 
consists of representable primes)
if and only if some quadratic form in 
one can prove that 
)
be a prime. Then 
.
if and only if 
.
. 
, and as before the only point is that the only reduced quadratic form for these 
is the principal one. 
. Then it 
. In that case we call the set of residue classes represented the 
.
represents 
. 
. It must be represented by one of these two quadratic forms, but the latter form is never 
and so it must be the first one. Thus we conclude that 
if and only if 
.
if and only if 
. 
are: 
elements of 
OR 
if and only if 
happen to have the same genus. 
of 
. As for 
is quite well-behaved: 
for some integer 
is the principal form then 
. Thus claim each element of 
be the number of distinct odd primes which divide 
by: 
if 
.
if 
.
.
if 
. 
. 
. Then there is a unique 
and bilinear forms 
for 
such that 
.
.
. 
and 
, and each choice of signs would yield one of four (possibly different) forms. So requiring both signs to be positive makes this operation well-defined. (This is why we like proper equivalence; it gives us a well-defined group structure, whereas with improper equivalence it would be impossible to put a group structure on the forms above.)
, 
is 
. 
and 
are inverses and that their 
images coincide (being improperly equivalent); this is expressed in the fact that 
. As another corollary, the number of elements of 
is 
. 
.
and 
, two examples of numbers which are not convenient.
is of the form ![{\mathbb Z[\omega]}](https://s0.wp.com/latex.php?latex=%7B%5Cmathbb+Z%5B%5Comega%5D%7D&bg=ffffff&fg=000000&s=0 "{\mathbb Z[\omega]}")
where 
, and 
is coprime to 
to be one such that 
; given any prime exactly one of the six associates is primary. We then have the following reciprocity theorem: 
are disjoint primary primes in 
, then 
) while the second reciprocity law handles the prime divisors of 
(analogous to 
.)
as follows. If 
, and thus we can put 
for some prime 
. Consequently, we have a natural isomorphism ![\displaystyle \mathbb Z[\omega] / \pi \mathbb Z[\omega] \cong \mathbb Z / p \mathbb Z.](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cmathbb+Z%5B%5Comega%5D+%2F+%5Cpi+%5Cmathbb+Z%5B%5Comega%5D+%5Ccong+%5Cmathbb+Z+%2F+p+%5Cmathbb+Z.+&bg=ffffff&fg=000000&s=0 "\displaystyle \mathbb Z[\omega] / \pi \mathbb Z[\omega] \cong \mathbb Z / p \mathbb Z.")
is a cubic residue if and only if 
.
. 
be primary, noting that 
for integers 
(check it!). Moreover, 
![{\mathbb Z[i]}](https://s0.wp.com/latex.php?latex=%7B%5Cmathbb+Z%5Bi%5D%7D&bg=ffffff&fg=000000&s=0 "{\mathbb Z[i]}")
, for which there are four units 
, 
. A prime is 
; every prime not dividing 
has a unique associate which is primary. Then we can as before define 
we have that 
thanks to the isomorphism ![\displaystyle \mathbb Z[i] / \pi \mathbb Z[i] \cong \mathbb Z / p \mathbb Z.](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cmathbb+Z%5Bi%5D+%2F+%5Cpi+%5Cmathbb+Z%5Bi%5D+%5Ccong+%5Cmathbb+Z+%2F+p+%5Cmathbb+Z.+&bg=ffffff&fg=000000&s=0 "\displaystyle \mathbb Z[i] / \pi \mathbb Z[i] \cong \mathbb Z / p \mathbb Z.")
is primary, then 
. 
and applying the above. Therefore 
is primary. We claim that 
was is divisible by 
, hence 
divides 
. Thus 
)
is prime, then 
with the following property: If 
are positive integers such that 
for all 
, then 
and the like. But the main idea is very simple: “consider an 
table of primes and note the small primes cannot adequately cover the board, since 
”. Once you have this main idea the technical estimates are just the grunt work that you force yourself to do if you’re a contestant (and don’t do if you’re retired like me).
points. The points are colored in four colors such that some 
points are colored Red, some 
be nine real numbers, not necessarily distinct, with average 
for which 
. What is the minimum possible value of 
table can be filled with one of the letters 
and 
in such a way that: 
be a positive integers. Prove that we must apply the Euler 
function at least 
times before reaching 
then 
is decreased by one and each of 
and 
are increased by one. In any case, if you look at this behavior for long enough you will see that the 
coordinate is a natural way to “track time” in successive 
(which is false) or something similar to this. I realized that had the students just ignored the task “prove 
” and spent some time getting a better understanding of the 
be a holomorphic function. A 
such that 
for all 
. A 
for all 
?
for any complex number 
such that 
. How can we pick one to use? For our ordinary square root function, we had a notion of “positive”, and so we simply took the positive root.
(here 
) we should take the root to be
; there are two choices for 
, differing by 
.
for each 
to lie in the right half of the complex plane. We see there is an obvious issue: there is a big discontinuity near the point 
and 
! The nearby point 
has been mapped very far away. This discontinuity occurs since the points on the negative real axis are at the “boundary”. For example, given 
, we send it to 
, but we have hit the boundary: in our interval 
, we are at the very left edge.
; then the ray of death would be the positive real axis instead. The earlier circle we had now works just fine.
be holomorphic. Then we want to decide whether there is a 
; there is a “half-ray” which causes problems. However, there are certainly functions 
such that a 
exists. As a simplest example, 
should definitely have a square root!
, pick a square root 
of 
, and then try to “fudge” from there the square roots of the other points. What do I mean by fudge? Well, suppose 
is a point very close to 
, and we want to pick a square root 
of 
. While there are two choices, we also would expect 
of 
and then ask you to continue this square root to 
, which sign should you pick for 
?)
, then we’re sunk. But even if we avoid that, we have to worry that we are in a situation, where we run around a full loop in the complex plane, and then find that our continuous perturbation has left us in a different place than we started. For concreteness, consider the following situation, again with 
.
. For 
, we already have the square root 
. So the burden is completing 
.
by 
are both punctured planes, we can identify them with 
.
once we identify 
.
in 
, we need 
to have an even winding number around 
. This amounts to
.
, then any complex number 
is also a solution.
is a universal cover, since 
is simply connected. Thus, 
is trivial. So in addition to being zero-free, 
be continuous, where 
is simply connected. If 
for every 
, then 
? Clearly 
(the point which we cannot circle around). This gives![\displaystyle \begin{aligned} \log &: \mathbb C \setminus (-\infty, 0] \rightarrow \mathbb C \\ \sqrt[n]{-} &: \mathbb C \setminus (-\infty, 0] \rightarrow \mathbb C \end{aligned}](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Cbegin%7Baligned%7D+%5Clog+%26%3A+%5Cmathbb+C+%5Csetminus+%28-%5Cinfty%2C+0%5D+%5Crightarrow+%5Cmathbb+C+%5C%5C+%5Csqrt%5Bn%5D%7B-%7D+%26%3A+%5Cmathbb+C+%5Csetminus+%28-%5Cinfty%2C+0%5D+%5Crightarrow+%5Cmathbb+C+%5Cend%7Baligned%7D+&bg=ffffff&fg=000000&s=0 "\displaystyle \begin{aligned} \log &: \mathbb C \setminus (-\infty, 0] \rightarrow \mathbb C \\ \sqrt[n]{-} &: \mathbb C \setminus (-\infty, 0] \rightarrow \mathbb C \end{aligned}")
); a choice of such a function is called a 
. For ![{(-\pi, \pi]}](https://s0.wp.com/latex.php?latex=%7B%28-%5Cpi%2C+%5Cpi%5D%7D&bg=ffffff&fg=000000&s=0 "{(-\pi, \pi]}")
(since we can shift by integer multiples of 
). Often, authors will write 
to emphasize this choice.![{[0,1]}](https://s0.wp.com/latex.php?latex=%7B%5B0%2C1%5D%7D&bg=ffffff&fg=000000&s=0 "{[0,1]}")
. Then the function 
by 
has a holomorphic square root.
or 
, depending on taste.
-manifold; the multiplication maps 
(by 
) and the inversion map 
(by 
) are required to be smooth.
denote the identity, or 
if we need further emphasis.
the connected component of 
. Then 
has the discrete topology.
be its universal cover. Then 
is a Lie group, 
.
under addition is a real one-dimensional Lie group.
is a real Lie group under multiplication.
is a Lie group of dimension 
. This example becomes important for representation theory: a 
.
is a Lie group of dimension 
.
by the natural map 
. There is another theorem worth noting, which is that:![{\mathbb C[G]}](https://s0.wp.com/latex.php?latex=%7B%5Cmathbb+C%5BG%5D%7D&bg=ffffff&fg=000000&s=0 "{\mathbb C[G]}")
is semisimple; all finite-dimensional representations decompose into irreducibles.
. Then we can average it to obtain a new inner form
we can just take its orthogonal complement to decompose 
doesn’t make sense, so we want to replace it with an integral 
instead. In order to do this we use the following:
and “translate” 
is the standard Lebesgue measure which assigns 
for 
.
is given by
![{\mu([a,b]) = \log(b/a)}](https://s0.wp.com/latex.php?latex=%7B%5Cmu%28%5Ba%2Cb%5D%29+%3D+%5Clog%28b%2Fa%29%7D&bg=ffffff&fg=000000&s=0 "{\mu([a,b]) = \log(b/a)}")
. One sees the invariance under multiplication of these intervals.
. Then a Haar measure is given by
. We can define
ensures 
.
.
, then 
. This now lets us deduce that
the tangent space to 
has a complex Lie algebra isomorphic to 
.
)
. Its tangent space should just be an 
)
first: then
in 
, we compute
is given by the orthogonal complement of the gradient
. In other words, we see
is just a vector space. However, by using the group structure we can get a map from 
there is a unique homomorphism
to emphasize the argument 
being thought of as “time”. Thus this proposition should be intuitively clear: the theory of differential equations guarantees that 
is defined and unique in a small neighborhood of 
. Then, the group structure allows us to extend 
. Note that below, 
for a matrix 
, then 
too. We observe 
(where 
) is a morphism of Lie groups 
. Hence
, the map 
given by 
works. Hence
, the map 
given by 
works nicely (now 
is actually invertible for this map to be well-defined.) Hence the exponential map is given by
, meaning 
, then 
. This can be seen by writing 
of Lie groups, with lie algebras 
and 
. Because 
. Now, by manifold theory we know that maps 
between manifolds gives 
. For us we obtain a linear map
fits into a diagram
:
, which is immediate by looking at the constant trajectory 
.
, i.e. the total derivative 
is the identity. This is again by construction.
, onto a neighborhood of 
, we can use it to put a new operation on 
and 
, which are two elements of 
for some unique 
.![\displaystyle \mu(x,y) = x + y + \frac{1}{2} [x,y] + \text{third order terms} + \dots](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Cmu%28x%2Cy%29+%3D+x+%2B+y+%2B+%5Cfrac%7B1%7D%7B2%7D+%5Bx%2Cy%5D+%2B+%5Ctext%7Bthird+order+terms%7D+%2B+%5Cdots+&bg=ffffff&fg=000000&s=0 "\displaystyle \mu(x,y) = x + y + \frac{1}{2} [x,y] + \text{third order terms} + \dots")
![{[x,y]}](https://s0.wp.com/latex.php?latex=%7B%5Bx%2Cy%5D%7D&bg=ffffff&fg=000000&s=0 "{[x,y]}")
is a skew-symmetric bilinear map, meaning ![{[x,y] = -[y,x]}](https://s0.wp.com/latex.php?latex=%7B%5Bx%2Cy%5D+%3D+-%5By%2Cx%5D%7D&bg=ffffff&fg=000000&s=0 "{[x,y] = -[y,x]}")
. It will be more convenient to work with ![{[,]}](https://s0.wp.com/latex.php?latex=%7B%5B%2C%5D%7D&bg=ffffff&fg=000000&s=0 "{[,]}")
. Specifically, since
, and this should tell us something. In fact, the claim is:![\displaystyle [x,[y,z]] + [y,[z,x]] + [z,[x,y]] = 0.](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Bx%2C%5By%2Cz%5D%5D+%2B+%5By%2C%5Bz%2Cx%5D%5D+%2B+%5Bz%2C%5Bx%2Cy%5D%5D+%3D+0.+&bg=ffffff&fg=000000&s=0 "\displaystyle [x,[y,z]] + [y,[z,x]] + [z,[x,y]] = 0.")
![\displaystyle \mu(x,y) = x + y + \frac{1}{2} [x,y] + \frac{1}{12} \left( [x, [x,y]] + [y,[y,x]] \right) + \text{fourth order terms} + \dots.](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Cmu%28x%2Cy%29+%3D+x+%2B+y+%2B+%5Cfrac%7B1%7D%7B2%7D+%5Bx%2Cy%5D+%2B+%5Cfrac%7B1%7D%7B12%7D+%5Cleft%28+%5Bx%2C+%5Bx%2Cy%5D%5D+%2B+%5By%2C%5By%2Cx%5D%5D+%5Cright%29+%2B+%5Ctext%7Bfourth+order+terms%7D+%2B+%5Cdots.+&bg=ffffff&fg=000000&s=0 "\displaystyle \mu(x,y) = x + y + \frac{1}{2} [x,y] + \frac{1}{12} \left( [x, [x,y]] + [y,[y,x]] \right) + \text{fourth order terms} + \dots.")
![{\mu\left( x, y + z + \frac{1}{2} [y,z] + \frac{1}{12} \left( [y,[y,z]] + [z,[z,y] \right) \right)}](https://s0.wp.com/latex.php?latex=%7B%5Cmu%5Cleft%28+x%2C+y+%2B+z+%2B+%5Cfrac%7B1%7D%7B2%7D+%5By%2Cz%5D+%2B+%5Cfrac%7B1%7D%7B12%7D+%5Cleft%28+%5By%2C%5By%2Cz%5D%5D+%2B+%5Bz%2C%5Bz%2Cy%5D+%5Cright%29+%5Cright%29%7D&bg=ffffff&fg=000000&s=0 "{\mu\left( x, y + z + \frac{1}{2} [y,z] + \frac{1}{12} \left( [y,[y,z]] + [z,[z,y] \right) \right)}")
, and the next step would be something ugly.![{-[y,x] = [x,y]}](https://s0.wp.com/latex.php?latex=%7B-%5By%2Cx%5D+%3D+%5Bx%2Cy%5D%7D&bg=ffffff&fg=000000&s=0 "{-[y,x] = [x,y]}")
by symmetry and ![{[x,y] = [y,x]}](https://s0.wp.com/latex.php?latex=%7B%5Bx%2Cy%5D+%3D+%5By%2Cx%5D%7D&bg=ffffff&fg=000000&s=0 "{[x,y] = [y,x]}")
from 
. Thus ![{[x,y] = 0}](https://s0.wp.com/latex.php?latex=%7B%5Bx%2Cy%5D+%3D+0%7D&bg=ffffff&fg=000000&s=0 "{[x,y] = 0}")
in 
are trivial.
. Then one can show that
![\displaystyle [T,S] = TS - ST \qquad \forall S, T \in \mathfrak{gl}(n, K).](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5BT%2CS%5D+%3D+TS+-+ST+%5Cqquad+%5Cforall+S%2C+T+%5Cin+%5Cmathfrak%7Bgl%7D%28n%2C+K%29.+&bg=ffffff&fg=000000&s=0 "\displaystyle [T,S] = TS - ST \qquad \forall S, T \in \mathfrak{gl}(n, K).")
.
Lie algebra)![{[a,b] = ab - ba}](https://s0.wp.com/latex.php?latex=%7B%5Ba%2Cb%5D+%3D+ab+-+ba%7D&bg=ffffff&fg=000000&s=0 "{[a,b] = ab - ba}")
.
is also an injective immersion.
of a Lie algebra ![{[\mathfrak h, \mathfrak h] \subseteq \mathfrak h]}](https://s0.wp.com/latex.php?latex=%7B%5B%5Cmathfrak+h%2C+%5Cmathfrak+h%5D+%5Csubseteq+%5Cmathfrak+h%5D%7D&bg=ffffff&fg=000000&s=0 "{[\mathfrak h, \mathfrak h] \subseteq \mathfrak h]}")
).
, the map
to a functor
and 
).
at all.
or 
. All of these operations turn out to be functors. This isn’t surprising, because as far as I’m concerned the definition of a functor is “any time you take one type of object and naturally make another object”.
is a functor
are ![{[f]}](https://s0.wp.com/latex.php?latex=%7B%5Bf%5D%7D&bg=ffffff&fg=000000&s=0 "{[f]}")
(the equivalence class under this relationship). This has the nice property that ![{[f \circ g] = [f] \circ [g]}](https://s0.wp.com/latex.php?latex=%7B%5Bf+%5Ccirc+g%5D+%3D+%5Bf%5D+%5Ccirc+%5Bg%5D%7D&bg=ffffff&fg=000000&s=0 "{[f \circ g] = [f] \circ [g]}")
and so on.
are 
and 
such that ![{[f \circ g] = [\mathrm{id}_X]}](https://s0.wp.com/latex.php?latex=%7B%5Bf+%5Ccirc+g%5D+%3D+%5B%5Cmathrm%7Bid%7D_X%5D%7D&bg=ffffff&fg=000000&s=0 "{[f \circ g] = [\mathrm{id}_X]}")
and ![{[g \circ f] = [\mathrm{id}_Y]}](https://s0.wp.com/latex.php?latex=%7B%5Bg+%5Ccirc+f%5D+%3D+%5B%5Cmathrm%7Bid%7D_Y%5D%7D&bg=ffffff&fg=000000&s=0 "{[g \circ f] = [\mathrm{id}_Y]}")
.
is defined as follows:
are homotopy classes of continuous maps 
of a map 
depends only on the homotopy class of 
is a functor
if 
for all 
. We will now show this is functorial too.
and 
be subspaces, and consider a map 
we write
and 
.
are 
is a map ![{F : [0,1] \times X \rightarrow Y}](https://s0.wp.com/latex.php?latex=%7BF+%3A+%5B0%2C1%5D+%5Ctimes+X+%5Crightarrow+Y%7D&bg=ffffff&fg=000000&s=0 "{F : [0,1] \times X \rightarrow Y}")
, which we’ll write as 
, such that 
is a homotopy of the maps 
and each 
is itself a map of pairs.
, the category of pairs of toplogical spaces, and
for 
. We say that 
which is a pair homotopy equivalence.
(when viewed as a map 
) is homotopic to the identity map 
.
deformation retracts onto its boundary 
deformation retracts onto its boundary 
.
deformation retracts onto a sphere 
is defined as follows:
of spaces 
. We call these 
, meaning 
.
of 
.
is 3-AP-free, then 
.
. Let ![{f : \mathbb Z/N \rightarrow [0,1]}](https://s0.wp.com/latex.php?latex=%7Bf+%3A+%5Cmathbb+Z%2FN+%5Crightarrow+%5B0%2C1%5D%7D&bg=ffffff&fg=000000&s=0 "{f : \mathbb Z/N \rightarrow [0,1]}")
with 
. Then
on vertices 
, where 
. Then one creates the edges
if 
,
if 
, and
if 
.
), the graph 
edges.
![\displaystyle \mathbf E[\nu] = 1 + o(1).](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Cmathbf+E%5B%5Cnu%5D+%3D+1+%2B+o%281%29.+&bg=ffffff&fg=000000&s=0 "\displaystyle \mathbf E[\nu] = 1 + o(1).")
, 
.
, then we let 
.
the tripartite graph defined earlier, and let 
; since 
in 
. Here 
![{\mathbf E[\mu_{-x}] = \mathbf E[\mu_{-y}] = \mathbf E[\mu_{-z}] = 1}](https://s0.wp.com/latex.php?latex=%7B%5Cmathbf+E%5B%5Cmu_%7B-x%7D%5D+%3D+%5Cmathbf+E%5B%5Cmu_%7B-y%7D%5D+%3D+%5Cmathbf+E%5B%5Cmu_%7B-z%7D%5D+%3D+1%7D&bg=ffffff&fg=000000&s=0 "{\mathbf E[\mu_{-x}] = \mathbf E[\mu_{-y}] = \mathbf E[\mu_{-z}] = 1}")
. Then we can define
satisfies the ![\displaystyle \begin{aligned} \mathbf E_{x^0,x^1,y^0,y^1,z^0,z^1} &\Big[ \mu_{-x}(y^0,z^0) \mu_{-x}(y^0,z^1) \mu_{-x}(y^1,z^0) \mu_{-x}(y^1,z^1) \\ & \mu_{-y}(x^0,z^0) \mu_{-y}(x^0,z^1) \mu_{-y}(x^1,z^0) \mu_{-y}(x^1,z^1) \\ & \mu_{-z}(x^0,y^0) \mu_{-z}(x^0,y^1) \mu_{-z}(x^1,y^0) \mu_{-z}(x^1,y^1) \Big] \\ &= 1 + o(1) \end{aligned}](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Cbegin%7Baligned%7D+%5Cmathbf+E_%7Bx%5E0%2Cx%5E1%2Cy%5E0%2Cy%5E1%2Cz%5E0%2Cz%5E1%7D+%26%5CBig%5B+%5Cmu_%7B-x%7D%28y%5E0%2Cz%5E0%29+%5Cmu_%7B-x%7D%28y%5E0%2Cz%5E1%29+%5Cmu_%7B-x%7D%28y%5E1%2Cz%5E0%29+%5Cmu_%7B-x%7D%28y%5E1%2Cz%5E1%29+%5C%5C+%26+%5Cmu_%7B-y%7D%28x%5E0%2Cz%5E0%29+%5Cmu_%7B-y%7D%28x%5E0%2Cz%5E1%29+%5Cmu_%7B-y%7D%28x%5E1%2Cz%5E0%29+%5Cmu_%7B-y%7D%28x%5E1%2Cz%5E1%29+%5C%5C+%26+%5Cmu_%7B-z%7D%28x%5E0%2Cy%5E0%29+%5Cmu_%7B-z%7D%28x%5E0%2Cy%5E1%29+%5Cmu_%7B-z%7D%28x%5E1%2Cy%5E0%29+%5Cmu_%7B-z%7D%28x%5E1%2Cy%5E1%29+%5CBig%5D+%5C%5C+%26%3D+1+%2B+o%281%29+%5Cend%7Baligned%7D+&bg=ffffff&fg=000000&s=0 "\displaystyle \begin{aligned} \mathbf E_{x^0,x^1,y^0,y^1,z^0,z^1} &\Big[ \mu_{-x}(y^0,z^0) \mu_{-x}(y^0,z^1) \mu_{-x}(y^1,z^0) \mu_{-x}(y^1,z^1) \\ & \mu_{-y}(x^0,z^0) \mu_{-y}(x^0,z^1) \mu_{-y}(x^1,z^0) \mu_{-y}(x^1,z^1) \\ & \mu_{-z}(x^0,y^0) \mu_{-z}(x^0,y^1) \mu_{-z}(x^1,y^0) \mu_{-z}(x^1,y^1) \Big] \\ &= 1 + o(1) \end{aligned}")
is satisfies the ![{\mathbf E[\nu] = 1 + o(1)}](https://s0.wp.com/latex.php?latex=%7B%5Cmathbf+E%5B%5Cnu%5D+%3D+1+%2B+o%281%29%7D&bg=ffffff&fg=000000&s=0 "{\mathbf E[\nu] = 1 + o(1)}")
, and the tripartite graph 
satisfies the 
bounded above by ![{\mathbf E[f] \ge \delta > 0}](https://s0.wp.com/latex.php?latex=%7B%5Cmathbf+E%5Bf%5D+%5Cge+%5Cdelta+%3E+0%7D&bg=ffffff&fg=000000&s=0 "{\mathbf E[f] \ge \delta > 0}")
, we have
, and ![{f : \mathbb Z/n \rightarrow [0,1]}](https://s0.wp.com/latex.php?latex=%7Bf+%3A+%5Cmathbb+Z%2Fn+%5Crightarrow+%5B0%2C1%5D%7D&bg=ffffff&fg=000000&s=0 "{f : \mathbb Z/n \rightarrow [0,1]}")
with ![{\mathbf E[f] \ge \delta}](https://s0.wp.com/latex.php?latex=%7B%5Cmathbf+E%5Bf%5D+%5Cge+%5Cdelta%7D&bg=ffffff&fg=000000&s=0 "{\mathbf E[f] \ge \delta}")
. Then
, rather than considering weighted tripartite graphs, we consider a 
-uniform 
, we use the construction
(i.e. a tetrahedron). We then consider the two-blow-up of the simplex, and require the same uniformity on subgraphs of 
satisfies the ![\displaystyle \mathbf E_{x_1^0, x_1^1, \dots, x_k^0, x_k^1} \left[ \prod_{j=1}^k \prod_{\omega \in \{0,1\}^{[k] \setminus \{j\}}} \mu_{-j}\left( x_1^{\omega_1}, \dots, x_{j-1}^{\omega_{j-1}}, x_{j+1}^{\omega_{j+1}}, \dots, x_k^{\omega_k} \right)^{n_{j,\omega}} \right] = 1 + o(1)](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Cmathbf+E_%7Bx_1%5E0%2C+x_1%5E1%2C+%5Cdots%2C+x_k%5E0%2C+x_k%5E1%7D+%5Cleft%5B+%5Cprod_%7Bj%3D1%7D%5Ek+%5Cprod_%7B%5Comega+%5Cin+%5C%7B0%2C1%5C%7D%5E%7B%5Bk%5D+%5Csetminus+%5C%7Bj%5C%7D%7D%7D+%5Cmu_%7B-j%7D%5Cleft%28+x_1%5E%7B%5Comega_1%7D%2C+%5Cdots%2C+x_%7Bj-1%7D%5E%7B%5Comega_%7Bj-1%7D%7D%2C+x_%7Bj%2B1%7D%5E%7B%5Comega_%7Bj%2B1%7D%7D%2C+%5Cdots%2C+x_k%5E%7B%5Comega_k%7D+%5Cright%29%5E%7Bn_%7Bj%2C%5Comega%7D%7D+%5Cright%5D+%3D+1+%2B+o%281%29+&bg=ffffff&fg=000000&s=0 "\displaystyle \mathbf E_{x_1^0, x_1^1, \dots, x_k^0, x_k^1} \left[ \prod_{j=1}^k \prod_{\omega \in \{0,1\}^{[k] \setminus \{j\}}} \mu_{-j}\left( x_1^{\omega_1}, \dots, x_{j-1}^{\omega_{j-1}}, x_{j+1}^{\omega_{j+1}}, \dots, x_k^{\omega_k} \right)^{n_{j,\omega}} \right] = 1 + o(1)")
.![\displaystyle \mathbf E_{x_1^0, x_1^1, \dots, x_k^0, x_k^1} \left[ \prod_{j=1}^k \prod_{\omega \in \{0,1\}^{[k] \setminus \{j\}}} \nu\left( \sum_{i=1}^k (j-i)x_i^{(\omega_i)} \right)^{n_{j,\omega}} \right] = 1 + o(1)](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Cmathbf+E_%7Bx_1%5E0%2C+x_1%5E1%2C+%5Cdots%2C+x_k%5E0%2C+x_k%5E1%7D+%5Cleft%5B+%5Cprod_%7Bj%3D1%7D%5Ek+%5Cprod_%7B%5Comega+%5Cin+%5C%7B0%2C1%5C%7D%5E%7B%5Bk%5D+%5Csetminus+%5C%7Bj%5C%7D%7D%7D+%5Cnu%5Cleft%28+%5Csum_%7Bi%3D1%7D%5Ek+%28j-i%29x_i%5E%7B%28%5Comega_i%29%7D+%5Cright%29%5E%7Bn_%7Bj%2C%5Comega%7D%7D+%5Cright%5D+%3D+1+%2B+o%281%29+&bg=ffffff&fg=000000&s=0 "\displaystyle \mathbf E_{x_1^0, x_1^1, \dots, x_k^0, x_k^1} \left[ \prod_{j=1}^k \prod_{\omega \in \{0,1\}^{[k] \setminus \{j\}}} \nu\left( \sum_{i=1}^k (j-i)x_i^{(\omega_i)} \right)^{n_{j,\omega}} \right] = 1 + o(1)")
satisfies the 
with 
. Then
which is near it:
. There exists 
such that if:
, and![{\widetilde f : \mathbb Z/N \rightarrow [0,1]}](https://s0.wp.com/latex.php?latex=%7B%5Cwidetilde+f+%3A+%5Cmathbb+Z%2FN+%5Crightarrow+%5B0%2C1%5D%7D&bg=ffffff&fg=000000&s=0 "{\widetilde f : \mathbb Z/N \rightarrow [0,1]}")
such that 
.
-uniform like before!): if 
is such a graph, we let
, 
gives the analogy.
be weighted 
. Assume that 
for all 
. If 
then![\displaystyle \mathbf E_{x_1, \dots, x_k} \left[ g(x_{-1}) \dots g(x_{-k}) - \widetilde g(x_{-1}) \dots \widetilde g(x_{-k}) \right] = o(1).](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Cmathbf+E_%7Bx_1%2C+%5Cdots%2C+x_k%7D+%5Cleft%5B+g%28x_%7B-1%7D%29+%5Cdots+g%28x_%7B-k%7D%29+-+%5Cwidetilde+g%28x_%7B-1%7D%29+%5Cdots+%5Cwidetilde+g%28x_%7B-k%7D%29+%5Cright%5D+%3D+o%281%29.+&bg=ffffff&fg=000000&s=0 "\displaystyle \mathbf E_{x_1, \dots, x_k} \left[ g(x_{-1}) \dots g(x_{-k}) - \widetilde g(x_{-1}) \dots \widetilde g(x_{-k}) \right] = o(1).")
. So we can find a nearby 
to the bounding of 
, which is 
by the usual Szemerédi theorem.
.
tend to infinity slowly with 
-trick
. The modified von Mangoldt function then is defined by
.
such that for 
prime, we can find 
.
instead of ![{\chi : \mathbb R \rightarrow [0,1]}](https://s0.wp.com/latex.php?latex=%7B%5Cchi+%3A+%5Cmathbb+R+%5Crightarrow+%5B0%2C1%5D%7D&bg=ffffff&fg=000000&s=0 "{\chi : \mathbb R \rightarrow [0,1]}")
be supported on ![{[-1,1]}](https://s0.wp.com/latex.php?latex=%7B%5B-1%2C1%5D%7D&bg=ffffff&fg=000000&s=0 "{[-1,1]}")
with 
, and define a normalizing constant 
. Inspired by 
, we define a truncated 
. Now, we define 
in 
but not 
linear algebra.
by selecting all-zero or all-one.
vs. 
decision problem for MAX-E3LIN is NP-hard.
or 
(given it is one or the other). A direct corollary of this is approximating MAX-SAT is also NP-hard.
vs. 
is optimal in light of a random assignment. In fact, one can replace 
, but we don’t do so here.
in MAX-E3LIN, we consider four formulas 
, 
, 
. Either three or four of them are satisfied, with four occurring exactly when 
. One does a similar construction for 
. We have
has a (non-adaptive) verifier with the following properties.
random bits, and queries just three (!) bits.
, then there is a proof 
which is accepted with probability at least 
, then every proof is accepted with probability at most 
.
, a set of keys 
there is a function 
specifying a key 
for every label 
. The goal is to label the graph 
vs. 
, given 
and 
are sufficiently large in 
in the resulting MAX-E3LIN.
, then we get a solution of value 
in the resulting MAX-E3LIN.
is a 
. An 
is defined similarly.
variables:
, we will create 
binary variables, one for every 
, we will create 
binary variables, one for every 
,
string by 
.
for the MAX-E3LIN instance.
and 
be the dictator functions for the colorings. In that case, 
, 
, and 
, so the product is always 
.
be a random 
with probability 
represents “noise” bits, which resolve the first problem by corrupting a bit of 
equations.
of the equations.
.
, we define
and that 
if 
is odd.
, then we can reconstruct a solution to LABEL-COVER with value 
. (The use of 
here will be clear in a moment). This process is called “decoding”.
is large, then we can pick a key from 
and 
. We want to do something similar with 
and 
be constants (the actual values arise later).
of keys is heavy for 
if
heavy sets by Parseval.
if
so at least one compatible key-label pair is in 
.
distribution.
of 
. In particular, 
. Finally by \Cref{rem:po}, we see 
. Note that 
, since there are at most 
, and select a random element from 
. Hence we conclude probability of success is at least
, but this doesn’t imply it for every edge. Thus one likely needs to do another averaging argument.)