Solution to Exercise of
Polynomial Methods in Combinatorics

Yuda Chen

(Date: August 24, 2025, only contains chapter 2,3,6,7,8,10)

The author would like to expressed his gratitude to Prof. Shaoming Guo, who held a wonderful seminar in 2025 Spring semester.

Solution 2.1.

We can show the general case directly.

Claim. Given any $N$ $k$-planes in ${ℝ}^n$ and there exists a non-zero polynomial of degree $\lesssim N^{\frac{1}{n-k}}$ that vanishes on all the $k$-planes.

Notice that, if a polynomial with degree of $D$ vanishes at $\left(\genfrac{}{}{0pt}{}{D+k}{k}\right)+1$ points on a same $k$-plane, then it will vanish on this $k$-plane. Therefore, there exists a non-zero polynomial satisfying the condition when $\left(\genfrac{}{}{0pt}{}{D+n}{n}\right)>N\left(\genfrac{}{}{0pt}{}{D+k}{k}\right)+N$, that is $D^n\gtrsim D^{k}N$, which means $D\lesssim N^{\frac{1}{n-k}}$. ∎

Solution 2.2.

Since the general process of proving the lemma using the Vandermonde determinant has been given in the question, we omit the proof using this method and instead use the proof of constructing the polynomial $f_j(x)$.

Define $D={\{|x_i-x_j|\}}_{x_i,x_j\in S,x_i\ne x_j}$ and $f_j(x)={\prod }_{d\in D}(x-d)$, then we have $f_j(x_i)=0$ if and only if $i\ne j$ so that we know $E_S$ is injective. Further, $E_S$ is an isomorphism.

Regarding the implication relation between the two lemmas, if $Q$ vanishes on every point in $S$, that is, $Q(x_i)=0$ for every $i$, we have $E_S(Q)=0$, which implies $Q=0$. ∎

Solution 2.3.

We will use induction to prove this lemma.

If $n=1$, we know $P$ have at most $D$ zero points. Now we proceed by induction on $n$. We can rewrite $P(x_1,x_2,\mathrm{\cdots },x_n)$ as $Q(x_n)={\sum }_{j=0}^D{P}_j(x_1,\mathrm{\cdots },x_{n-1})x_n^j$. And we know $Z(P)={\bigcup }_{a_n\in A_n}\{x\in Z(P)\mid x_n=a_n\}={\bigcup }_{a_n\in A_n}\{(x_1,\mathrm{\cdots },x_{n-1},a_n)\mid (x_1,\mathrm{\cdots },x_{n-1})\in Z(Q(a_n))\}$, so we have $|Z(P)|={\sum }_{a_n\in A_n}\mathrm{\#}\{(x_1,\mathrm{\cdots },x_{n-1},a_n)\mid (x_1,\mathrm{\cdots },x_{n-1})\in Z(Q(a_n))\}\le N\cdot D{N}^{(n-1)-1}=D{N}^{n-1}$ by induction hypothesis. ∎

Solution 2.4.

¹¹ 1 This part of the proof comes from [3].

We will use induction to prove this conclusion. Suppose this conclusion is established for polynomials in $n-1$ variables. We can rewrite $P(x,x_n)={\sum }_{j=0}^d{P}_j(x)x_n^j$, where $x=(x_1,\mathrm{\cdots },x_{n-1})$. Notice that, if $(x,x_n)\in Z(P)$, then $x,x_n$ must satisfy at least one condition:
(1) For any $i=0,\mathrm{\cdots },d$, $P_i(x)=0$
(2) Fix $x$, then $x_n\in Z\left({\sum }_{j=0}^d{P}_j(x)x_n^j\right)$ (Notice that ${\sum }_{j=0}^d{P}_j(x)x_n^j\not\equiv 0$).

First, We assume $E=\{(x,x_n)\mid x\text{ satisfies condition (1)}\}$ and $F=\{(x,x_n)\mid x_n,x\text{ satisfy condition (2)}\}$. By inductive hypothesis, we know $m(E)=0$. For any fixed $x$, we know there only exist at most $d$ roots of ${\sum }_{j=0}^d{P}_j(x)x_n^j$ by fundamental theorem of algebra. Now applying Fubini’s theorem then we have $m(F)=0$, which leads $m(Z(P))=m(E\cup F)=0$. ∎

Solution 2.5.

We can take $c(d,n)=\frac{1}{2^n{(d+1)}^{n}n!}$. If this conclusion isn’t established, assuming $k=\min (d,q-1)$, we can find $P\in {\mathrm{Poly}}_D({𝔽}_q^n)$ that vanishes at all points in ${\bigcup }_{a\in {𝔽}_q^n}{\mathrm{\Gamma }}_a$ with $D=\lfloor \frac{q}{k+1}\rfloor \ge 1$ because

$$\left(\genfrac{}{}{0pt}{}{D+n}{n}\right)\ge \frac{{\lfloor \frac{q}{k+1}\rfloor }^n}{n!}\ge \frac{q^n}{2^n{(k+1)}^{n}n!}\ge \frac{1}{2^n{(d+1)}^{n}n!}{q}^n=c(d,n)q^n>\left|\bigcup _{a\in {𝔽}_q^n}{\mathrm{\Gamma }}_a\right|$$

We can also assume that $d_{a,j}=\mathrm{deg}{Q}_{a,j}$ won’t exceed $q-1$ (if not, we can assume $d_{a,j}^{\prime }$ as $d_{a,j}-\lfloor \frac{d_{a,j}}{q-1}\rfloor (q-1)$ to replace $d_{a,j}$). Further, we have $d_{a,j}\le k$ and $\mathrm{deg}{Q}_{P,a}\le Dk\le q-D\le q-1$ if assuming $Q_{P,a}(t)=P(Q_{a,1}(t),\mathrm{\cdots },Q_{a,n-1}(t),t)$.

Claim. If $P\in {\mathrm{Poly}}_D({𝔽}_q^n)$ that vanishes at all points in ${\bigcup }_{a\in {𝔽}_q^n}{\mathrm{\Gamma }}_a$, then we have $x_n|P(x_1,\mathrm{\cdots },x_n)$ and $\frac{P(x_1,\mathrm{\cdots },x_n)}{x_n}$ also vanishes at all points in ${\bigcup }_{a\in {𝔽}_q^n}{\mathrm{\Gamma }}_a$.

Because of $(a,0)\in {\mathrm{\Gamma }}_a$ for any $a\in {𝔽}_q^{n-1}$, $P(a,0)=0$ holds for any $a\in {𝔽}_q^{n-1}$, that is, $x_n|P(x_1,\mathrm{\cdots },x_n)$. If we assume $P_1(x_1,\mathrm{\cdots },x_n)=\frac{P(x_1,\mathrm{\cdots },x_n)}{x_n}$, we have $\mathrm{deg}{Q}_{P_1,a}\le q-2$. Now take $t=1,\mathrm{\cdots },q-1$ and we know $Q_{P_1,a}(t)=\frac{Q_{P,a}(t)}{t}=0$ for any $a\in {𝔽}_q^{n-1}$. Further, we know $Q_{P_1,a}(0)=0$ for any $a\in {𝔽}_q^{n-1}$, that is, $P_1(a,0)=0$, which means $\frac{P(x_1,\mathrm{\cdots },x_n)}{x_n}$ also vanishes at all points in ${\bigcup }_{a\in {𝔽}_q^n}{\mathrm{\Gamma }}_a$.

If we assume that $P$ is the polynomial with the lowest degree satisfying that $P$ vanishes at all points in ${\bigcup }_{a\in {𝔽}_q^n}{\mathrm{\Gamma }}_a$, we have $\mathrm{deg}P=0$, implying $P\equiv 0$, which causes the contradiction. ∎

Solution 2.6.

Assuming the maximum number of joints generated by $L$ lines is $J_L$, then we have the following claim.

Claim. There exists one line with at most $n{J}_L^{\frac{1}{n}}$ joints.

First we know we can find a non-zero polynomial $P$ with degree at most $n{J}_L^{\frac{1}{n}}$ vanishing at every joint. (Let $P$ be the polynomial with the lowest degree that satisfies this condition.) If every line contains over $n{J}_L^{\frac{1}{n}}$ joints, then $P$ vanishes on every line. So we know $\nabla P$ also vanish on every joint. Due to the minimum degree of $P$, we have $\mathrm{deg}P=0$, which leads a contradiction.

Now we can know $J_L\le {(nL)}^{\frac{n}{n-1}}$ from

$$J_L\le J_{L-1}+n{J}_L^{\frac{1}{n}}\le J_{L-2}+2n{J}_L^{\frac{1}{n}}\le \mathrm{\cdots }\le nL{J}_L^{\frac{1}{n}}$$

∎

Solution 2.7.

We assume that set $X$ contains all the joints. For each coordinate axis $j$, define the indicator function $f_j:ℝ\to \{0,1\}$ as:

Then we know ${\sum }_{x_j\in ℝ}{f}_j(x_j)=|{\pi }_j(X)|\le |{𝔏}_j|$ and the cardinality of $X$ can be expressed as:

$$|X|=\sum _{(x_1,x_2,\mathrm{\dots },x_n)\in X}1=\sum _{x_1,x_2,\mathrm{\dots },x_n}{f}_1(x_1)f_2(x_2)\mathrm{\cdots }{f}_n(x_n).$$

For $n$ non-negative functions $f_1,f_2,\mathrm{\dots },f_n$, Hölder’s inequality states:

$$\sum _{x_1,\mathrm{\dots },x_n}{f}_1(x_1)f_2(x_2)\mathrm{\cdots }{f}_n(x_n)\le \prod _{j=1}^n{\left(\sum _{x_j}{f}_j{(x_j)}^{n-1}\right)}^{\frac{1}{n-1}}.$$

Notice that ${\left({\sum }_{x_j}{f}_j{(x_j)}^{n-1}\right)}^{\frac{1}{n-1}}={\left({\sum }_{x_j\in {\pi }_j(X)}1\right)}^{\frac{1}{n-1}}={|{𝔏}_j|}^{\frac{1}{n-1}}$, so we have $|X|\le {\prod }_{j=1}^n{|{𝔏}_j|}^{\frac{1}{n-1}}$, which finishes the proof. ∎

Solution 2.8.

It’s trivial that $P$ vanishes at all points. If there exist a polynomial $Q(x_1,x_2,x_3)$ with $\mathrm{deg}Q\le |A|$, we can rewrite it as ${\sum }_{i=0}^{|A|-1}{Q}_i(x_2,x_3)x_1^i$ and get $Q_i(x_2,x_3)\equiv 0$ for any $i$, from $Q$ vanishing at $|A|$ points when $x_2$ and $x_3$ are fixed. And we can rewrite $Q_i(x_2,x_3)$ as ${\sum }_{j=0}^{|A|-i}{Q}_{ij}(x_3)x_2^j$. Similarly, we know $Q_{ij}\equiv 0$ for any $j$. Then we have $Q\equiv 0$, which leads a contradiction.

Now we know that every minimal degree polynomial $Q$ vanishing on the grid has degree of $|A|$. Consider that for every fixed $x_2$ and $x_3$, we have ${\prod }_{a\in A}(x_1-a)\mid Q$. Then $Q(x_1,x_2,x_3)$ must be form of $R(x_1,x_2,x_3){\prod }_{a\in A}(x_1-a)$. Considering the degree, we know $R(x_1,x_2,x_3)$ is a constant, that is, $Q$ is a multiple of $P$.

For the case of $|A|=|B|=|C|$, we will prove this conclusion: for every minimal degree polynomial $P$ vanishing on the grid, $P$ must be the form of

$$c_1\prod _{a\in A}(x_1-a)+c_2\prod _{b\in B}(x_2-b)+c_3\prod _{c\in C}(x_3-c)$$

²² 2 This part of the proof comes from [7].

Assuming $|A|=|B|=|C|=n$, we can rewrite

$$P(x_1,x_2,x_3)=c_1\prod _{a\in A}(x_1-a)+c_2\prod _{b\in B}(x_2-b)+c_3\prod _{c\in C}(x_3-c)+Q(x_1,x_2,x_3)$$

where $Q$ satisfying:
(1) Its degree is at most $n$;
(2) None of its monomials contains the $n$th power of a single variable;
(3) It vanishes on any combination where each of its variables is drawn from a fixed set of $n$ distinct points.

Claim. Any polynomial $Q(x_1,\mathrm{\cdots },x_m)$ satisfying these three properties must be the zero polynomial.

We will prove this conclusion by induction on the number of variables. It’s obvious that the conclusion establish when $m=1$ because we know it has degree at most $n-1$ from condition (1) and (2). Suppose that the conclusion holds for polynomials with $m-1$ variables. Let $Q(x_1,\mathrm{\cdots },x_m)$ satisfy the three conditions and vanish on $A_1\times \mathrm{\cdots }\times A_m$ where $|A_k|=n$. Now we can rewrite $Q$ as ${\sum }_{k=0}^{n-1}{Q}_k(x_1,\mathrm{\cdots },x_{m-1})x_m^k$, then we know $Q_k(x_1,\mathrm{\cdots },x_{m-1})\equiv 0$ by ${\mathrm{deg}}_{x_m}Q\le n-1$ and condition (3). Then we know that $Q_k$ vanishes on $A_1\times \mathrm{\cdots }\times A_{m-1}$ and also satisfies condition (1) and (2), for any $k$. Now we can know $Q_k\equiv 0$ by induction hypothesis, which finishes the proof.

Finally, let $m=3$ and the proof of the conclusion is completed. ∎

Solution 2.9.

The conclusion of this exercise can be fully supported by the proof presented in [8]. ∎

Solution 3.1.

Firstly, we can define $⟨v,w⟩$ in ${𝔽}_q^3$ as $v\cdot \overline{w}$, which equals to ${\sum }_{i=1}^3{v}_i{w}_i^p$, so every point $x$ on the Hermitian variety satisfies $⟨x,x⟩=1$.

Claim. For any $v,w\in H$, there exist $g\in U({𝔽}_q^3)$ satisfying $gv=w$.

For any $v\in H$, we can extend it to an orthonormal basis $\{v,e_2,e_3\}$ satisfying

$$⟨v,v⟩=1,⟨v,e_i⟩=0,⟨e_i,e_j⟩={\delta }_{ij}$$

Also, we can construct another orthonormal basis $\{w,f_2,f_3\}$ satisfying

$$⟨w,w⟩=1,⟨w,f_i⟩=0,⟨f_i,f_j⟩={\delta }_{ij}$$

Then let $g(v)=w,g(e_2)=f_2,g(e_3)=f_3$, it’s obvious that $g$ keeps the inner product, which implies $U({𝔽}_q^3)$. Now we know this group action is transitively. ∎

Solution 3.2.

Firstly, about the number of points on hypersurface $Q$, we can rewrite the equation as $x_1^2+x_2^2=1+x_3^2+x_4^2$ and let $1+x_3^2+x_4^2=c$. By results in [6], we know the equation $x_1^2+x_2^2=c$ has $\sim q$ solutions for $(x_1,x_2)$ if $c$ is fixed. Allow $x_3$ and $x_4$ to vary, then we know the number of the solutions is $\sim q^3$, which means there are $\sim q^3$ points on $Q$.

Secondly, about the number of lines lying on $Q$, we need the following claim.

Claim. Each point of $Q$ lies on $\sim q$ lines.

Consider that ${\left(x_1+v_{1}t\right)}^2+{\left(x_2+v_{2}t\right)}^2-{\left(x_3+v_{3}t\right)}^2-{\left(x_4+v_{4}t\right)}^2=1$ always holds for every $t$, it implies $x_1{v}_1+x_2{v}_2-x_3{v}_3-x_4{v}_4=0$ and $v_1^2+v_2^2-v_3^2-v_4^2=0$. Let $S_r=\{(v_1,v_2,v_3,v_4)\in {𝔽}_q^4\mid v_1^2+v_2^2=v_3^2+v_4^2=r\}$ and it’s obvious that $S_r$ contains $\sim q^2$ points for fixed $r$ by [6]. Notice that $x_1{v}_1+x_2{v}_2-x_3{v}_3-x_4{v}_4=0$ are linear for $(v_1,v_2,v_3,v_4)$, so the number of points on $S_r$ satisfying the above linear equation is $\sim q$. Allow $r$ to vary from $0$ to $q-1$, we know the number of solutions for $(v_1,v_2,v_3,v_4)$ of initial equations is $\sim q^2$. And because the above equations which contain $v_i$ are all homogeneous, there are only $\sim \frac{q^2}{q-1}\sim q$ different directions, that is, each point corresponds to $\sim q$ lines.

Because each point contributes $\sim q$ lines and there are $\sim q^3$ points on $Q$, each line is shared by $q$ points. Now we know there are $\sim$ $\frac{q^3\cdot q}{q}=q^3$ lines on $Q$.

Finally, regarding of fact that the lines through each point $x\in Q$ lie in a 3 -plane, we can know every line passing $x$ is in $x_1{v}_1+x_2{v}_2-x_3{v}_3-x_4{v}_4=0$, which is a 3 -plane, by the knowledge of linear algebra. ∎

Solution 3.3.

For the case of $n=1$, we can consider the linear map $E:W\to {𝔽}^{D+1},f\mapsto (f(x_0),\mathrm{\cdots },f(x_D))$. If $dimW\ge D+2$, then there exist linear independent functions $f_1,\mathrm{\cdots },f_{dimW}\in \mathrm{Fcn}(𝔽,𝔽)$, and we know $dim\ker E+dim\mathrm{Im}E=dimW$ by Rank-Nullity Theorem, which leads $dim\ker E\ge 1$. So there exists a non-zero function $g=c_1{f}_1+\mathrm{\cdots }+c_{dimW}{f}_{dimW}$ satisfying $E(g)=0$, which is a contradiction.

When $n\ge 2$, we assume that the case of $n-1$ is established. If regarding $P(t_1,\mathrm{\cdots },t_n)$ as a function with respect to $t_n$, we have

$$P(t_1,\mathrm{\cdots },t_n)=\sum _{k=0}^D{P}_k(t_1,\mathrm{\cdots },t_{n-1})t_n^k$$

where $P_k\in \mathrm{Fcn}({𝔽}^{n-1},𝔽)$ (the reason why we can make this decomposition is that $\{1,t_n,\mathrm{\cdots },t_n^k\}$ forms a group of basis). Notice that $P_k$ satisfies vanishing lemma of degree $D$, we have

$$dimW\le \underset{\text{choices of }{P}_0}{\underbrace{{(D+1)}^{n-1}}}+\underset{\text{choices of }{P}_1}{\underbrace{{(D+1)}^{n-1}}}+\mathrm{\cdots }+\underset{\text{choices of }{P}_D}{\underbrace{{(D+1)}^{n-1}}}={(D+1)}^n$$

according to the induction hypothesis. ∎

Solution 6.1.

We use the Bezout theorem in [4] to prove the following claim.

Claim. If , then the theorem is still true when $|𝔽|$ is finite.

Firstly, we know

$$\sum _{j}i(Y,H;Z_j)\cdot \mathrm{deg}{Z}_j=\mathrm{deg}Y\cdot \mathrm{deg}H$$

from [4]. We consider $P=0$ and $Q=0$ as algebraic curve defined in $\overline{{𝔽}_q}$ and here $Y=V(P),H=V(Q)\subset {\overline{{𝔽}_q}}^2$. So for every line in initial $Z(P,Q)$, it’s also in the ”new $Z(P,Q)$”.

Let lines be $L_1,\mathrm{\dots },L_r\subset Y\cap H$ and now

$$\sum _{j=1}^{r}i(Y,H;Z_j)\cdot \mathrm{deg}{Z}_j\le d_1{d}_2$$

Because $Z_j$ are lines on $P=0$ and $Q=0$, $\mathrm{deg}{Z}_j=1$ and $i(Y,H;Z_j)\ge 1$ hold. So

$$\sum _{j=1}^{r}i(Y,H;Z_j)\cdot \mathrm{deg}{Z}_j=\sum _{j=1}^{r}i(Y,H;Z_j)\ge r$$

which means

$$r\le \sum _{j}i(Y,H;Z_j)\cdot \mathrm{deg}{Z}_j\le d_1{d}_2$$

Notice that the lines in initial $Z(P,Q)$ are all in ${\{L_i\}}_{i=1}^r$ then the claim is true. ∎

Solution 6.2.

For the first question, parameterize curve $P(𝔽)$ as $(P_1(t),P_2(t))$ and define polynomials

$$f(t)=P_1(t)-x,g(t)=P_2(t)-y,$$

here $x,y$ are varible. Because $\mathrm{deg}{P}_1\le D$ and $\mathrm{deg}{P}_2\le D$, we have ${\mathrm{deg}}_{t}f\le D$ and ${\mathrm{deg}}_{t}g\le D$. So resultant ${\mathrm{res}}_t(f,g)$ is polynomial wrt $x,y$ and let $Q(x,y)={\mathrm{res}}_t(f,g)$. When $(x,y)=(P_1(t),P_2(t))$, we know $f$ and $g$ have common root $t$, then the resultant equals to 0. So $Q(P_1(t),P_2(t))=0$ holds for every $t$, which means $P(𝔽)\subseteq Z(Q)$. Consider the form of resultant (a $2D\times 2D$ determinant), we know $x,y$ only appear in the right $D$ columns, so $\mathrm{deg}Q\le D$.

For the second question, firstly parameterize $H$:

$$s(u)=\frac{u^2+1}{2u},t(u)=\frac{u^2-1}{2u},$$

and here $u\in 𝔽\setminus \{\pm 1\}$, then let

$$X(u)=P_1(s(u),t(u)),Y(u)=P_2(s(u),t(u)).$$

Let $X(u)=A(u)/C(u)$ and $Y(u)=B(u)/D(u)$, here $A,B,C,D$ are polynomials and $\mathrm{deg}A,\mathrm{deg}C\le 2D$, $\mathrm{deg}B,\mathrm{deg}D\le 2D$.

$$f(u)=C(u)x-A(u),g(u)=D(u)y-B(u).$$

Now let $Q(x,y)={\mathrm{res}}_u(f,g)$. Notice that $C(u)$ and $D(u)$ are all like ${(2u)}^k$ and $k\le D$. Similar as the first proof, just consider the $4D\times 4D$ determinant, we know $\mathrm{deg}Q\le 2D$ because there are only $2D$ columns containing $x,y$.

For the general case, if $P:H\to {𝔽}^k$ is a polynomial map where $H$ is a curve or (hyper)surface with dimension of $r$ and degree of $m$, and every $\mathrm{deg}{P}_i$ is not more than $D$, then there exist $Q$ such that $P(H)\subseteq Z(Q)$ and $\mathrm{deg}Q\le m{D}^r$. The details of proof can be read here: [1]. ∎

Solution 7.1.

³³ 3 Hint of this problem may has defect. This solution has fixed that.

Using the hint of exercise, for an integer $a\ge 2$, let $D(a,Q)$ be the set of pairs $(p,q)$ with , and so that $a$ divides both $p$ and $q$. So we have $|D(a,Q)|\le \left(\genfrac{}{}{0pt}{}{\lfloor \frac{Q}{a}\rfloor }{2}\right)\le \left(\genfrac{}{}{0pt}{}{Q}{2}\right)a^{-2}$.

Note that $R(Q)$ can be formed by starting with all pairs $(p,q)$ with $q\le Q$ and then removing $D(a,Q)$ for every prime $a$. Therefore,

$$|R(Q)|\ge \left(\genfrac{}{}{0pt}{}{Q}{2}\right)-\sum _{a\text{ prime}}|D(a,Q)|\ge \left(1-\sum _{a\ge 2,\text{ prime}}{a}^{-2}\right)\left(\genfrac{}{}{0pt}{}{Q}{2}\right)$$

When $Q\ge 5$, we have $\left(\genfrac{}{}{0pt}{}{Q}{2}\right)=\frac{Q-1}{Q}\cdot \frac{Q^2}{2}\ge \frac{2}{5}{Q}^2$, which means we only need prove that $1-{\sum }_{a\ge 2,\text{ prime}}{a}^{-2}\ge \frac{1}{4}$. And we can use to finish this proof. When $Q=2,3,4$, the ratios are $\frac{1}{4},\frac{1}{3},\frac{5}{16}$ respectively. So we have $|R(Q)|\ge \frac{1}{10}{Q}^2$. ∎

Solution 7.2.

Let $S^{\prime }(r)$ be the set of fractions in $S(r)$ whose numerator and denominator are both at least $\frac{r^{\frac{1}{2}}}{10}$. We will state that $|S^{\prime }(r)|\ge \frac{r}{2}$. We only need to prove that there are no more than $\frac{r}{2}$ fractions whose numerator or denominator is less than $\frac{\sqrt{r}}{10}$. Notice that ${\sum }_{k=1}^n\phi (k)\ge \frac{n^2}{4}$ (just consider $\phi (k)\ge \frac{k+1}{2}$ for odd $k$), then every fraction in $S^{\prime }(r)$ has a denominator less than $\sqrt{4r}$. So there are at most $\frac{\sqrt{r}}{10}\cdot \sqrt{4r}\le \frac{r}{5}$ fractions with numerator greater than $\frac{\sqrt{r}}{10}$ and at most fractions with denominator greater than $\frac{\sqrt{r}}{10}$. Sum them up then we know the conclusion is true.

Let ${𝔏}_{N,r}^{\prime }\subseteq {𝔏}_{N,r}$ be the lines with slope in $S^{\prime }(r)$. Then every line with slope of $\frac{p}{q}$ in ${𝔏}_{N,r}^{\prime }$ intersects the $N\times N$ grid $G_N$ at most $1+\min (\frac{N-1}{p},\frac{N-1}{q})\le 1+\frac{10N}{\sqrt{r}}\lesssim N{r}^{-\frac{1}{2}}$ points. But every point in $G_N$ lies in at least $\frac{r}{2}$ lines of ${𝔏}_{N,r}^{\prime }$. By double counting, we know $|{𝔏}_{N,r}|\ge |{𝔏}_{N,r}^{\prime }|\ge \frac{N^2}{\frac{N{r}^{-\frac{1}{2}}}{\frac{r}{2}}}\sim N{r}^{\frac{3}{2}}$, so the proof finishes. ∎

Solution 7.3.

Every line in $\mathbb{P}{𝔽}_q^2$ can be written as $ax+by+cz=0$ where $[x,y,z]$ represents point on the line and $(a,b,c)\ne (0,0,0)$. Then line $a_{1}x+b_{1}y+c_{1}z=0$ intersects line $a_{2}x+b_{2}y+c_{2}z=0$ at only $[b_2{c}_1-b_1{c}_2,a_1{c}_2-a_2{c}_1,a_2{b}_1-a_1{b}_2]$. Also, for a fixed point $[x,y,z]$ in $\mathbb{P}{𝔽}_q^2$, because $\frac{b}{a}$ can take $q+1$ different values (including $\mathrm{\infty }$), there are $q+1$ different lines in $\mathbb{P}{𝔽}_q^2$ passing it. Then we know $|P_{q+1}𝔏|=\frac{\left(\genfrac{}{}{0pt}{}{|𝔏|}{2}\right)}{\left(\genfrac{}{}{0pt}{}{q+1}{2}\right)}$ immediately. ∎

Solution 7.4.

With some simple calculation, we know $L\sim Hr$. For every $(x_0,y_0)$ satisfying $|x_0|\le H{r}^{-1}$ and $|y_0|\le H$, we have $y=mx+(y_0-m{x}_0)$ passing $(x_0,y_0)$, for $m=1,2,\mathrm{\cdots },r$ (notice that $|y_0-m{x}_0|\le 2H$), which means every $(x_0,y_0)$ is an $r$-rich point. So $P_r(𝔏)\gtrsim H{r}^{-1}\cdot H\sim L^2{r}^{-3}$. ∎

Solution 7.5.

Take $𝒮=P_r(𝔏)$ in Theorem 7.11 and then we have $I(P_r,𝔏)\lesssim S^{\frac{2}{3}}{L}^{\frac{2}{3}}+S+L$. Also, we have trivial bound of $I(P_r,𝔏)\ge Sr$ (for every point, only consider the $r$ lines passing through it). Now we have $Sr\lesssim S^{\frac{2}{3}}{L}^{\frac{2}{3}}+S+L$. Because , we have $S^{\frac{2}{3}}{L}^{\frac{2}{3}}>S$.

If $S^2\le L$, which implies $L\ge S^{\frac{2}{3}}{L}^{\frac{2}{3}}$, we have $Sr\lesssim L$, that is, $S\lesssim L{r}^{-1}$.

If $S^2\ge L$, which implies $L\le S^{\frac{2}{3}}{L}^{\frac{2}{3}}$, we have $Sr\lesssim S^{\frac{2}{3}}{L}^{\frac{2}{3}}$, that is, $S\lesssim L^2{r}^{-3}$.

Then we have $|P_r(𝔏)|=S\lesssim L{r}^{-1}+L^2{r}^{-3}$, which is Theorem 7.1. ∎

Solution 7.6.

Using $𝔏$ and $𝒮$ we construct a graph drawn in the plane. The vertices of our graph $G$ are the points of $𝒮$. We join two vertices with an edge of $G$ if the two points are two consecutive points of $𝒮$ along a line $\mathrm{\ell }\in 𝔏$. We let $k_{\mathrm{\ell }}$ denote the number of points on $\mathrm{\ell }$. Notice that $|I(𝒮,𝔏)|={\sum }_{\mathrm{\ell }\in 𝔏}{k}_{\mathrm{\ell }}-1$ and $E={\sum }_{\mathrm{\ell }\in 𝔏}\max (k_{\mathrm{\ell }}-1,0)$, we have $|I(𝒮,𝔏)|\le E+L$. The crossing number of this drawing is at most $\left(\genfrac{}{}{0pt}{}{L}{2}\right)\le L^2$, since each crossing of the graph $G$ must correspond to an intersection of two lines of $𝔏$. This is also a straight line drawing. So we see that $L^2\ge k_{str}(G)$.

Claim. We have $E\le \max (4L^{\frac{2}{3}}{S}^{\frac{2}{3}},4S)$.

If $E\ge 4S$, we can apply the estimate $k_{str}(G)\ge \frac{1}{64}{E}^3{S}^{-2}$, then we get $L^2\ge \frac{1}{64}{E}^3{S}^{-2}$, which means $E\le 4L^{\frac{2}{3}}{S}^{\frac{2}{3}}$. If , the conclusion holds naturally.

Now we know $I(𝒮,𝔏)\le E+L\lesssim S^{\frac{2}{3}}{L}^{\frac{2}{3}}+S+L$ immediately. ∎

Solution 7.7.

Proof by Theorem 7.11: Take $𝔏={𝔏}_r$ in Theorem 7.11 and then we have $I(𝒮,{𝔏}_r)\lesssim S^{\frac{2}{3}}{L}^{\frac{2}{3}}+S+L$. Also, we have trivial bound of $I(𝒮,{𝔏}_r)\ge Lr$ (for every line, only consider the $r$ points lying on it). Now we have $Lr\lesssim S^{\frac{2}{3}}{L}^{\frac{2}{3}}+S+L$. Because , we have $S^{\frac{2}{3}}{L}^{\frac{2}{3}}>L$. If $L^2\le S$, which implies $S\ge L^{\frac{2}{3}}{S}^{\frac{2}{3}}$, we have $Lr\lesssim S$, that is, $L\lesssim S{r}^{-1}$. If $L^2\ge S$, which implies $S\le L^{\frac{2}{3}}{S}^{\frac{2}{3}}$, we have $Lr\lesssim L^{\frac{2}{3}}{S}^{\frac{2}{3}}$, that is, $L\lesssim S^2{r}^{-3}$. So the conclusion is established.

Proof by Theorem 7.1: Consider the polarity transformation

$$f:(a,b)\mapsto ax+by=1,ax+by+c=0\mapsto (-\frac{a}{c},-\frac{b}{c})$$

where $c\ne 0$, assuming $𝒮,𝔏$ both don’t contain or pass origin point, we have $f(𝒮)$ is a set of lines and $f(𝔏)$ is a set of points. And for every point $Q$, we have $f(Q)$ passing $Q$. For every line $\mathrm{\ell }$, we have $f(\mathrm{\ell })$ lying on $\mathrm{\ell }$. By Theorem 7.1, we know $|P_r(𝔏)|\lesssim L{r}^{-1}+L^2{r}^{-3}$. We get the conclusion since

$$|{𝔏}_r|=|f(P_r(f(𝒮)))|=|P_r(f(𝒮))|\lesssim |f(𝒮)|r^{-1}+{|f(𝒮)|}^2{r}^{-3}=S{r}^{-1}+S^2{r}^{-3}$$

∎

Solution 7.8.

Let $S={[x_i,y_i,z_i]}_{i=1}^n$, there must exist $\alpha \in ℝ$ such that $x_i+\alpha y_i+{\alpha }^2{z}_i\ne 0$ for $i=1,2,\mathrm{\cdots },n$ (just let $\alpha$ not equal to the root of $x_i+\alpha y_i+{\alpha }^2{z}_i=0$ for every $i$). So the projective transformation

can map $S$ to a set in ${ℝ}^2$. Because projective transformation don’t change the number of lines, points and incidences, directly, we know that Szemeredi-Trotter Theorem of $ℝ{\mathbb{P}}^2$ version holds. Because every line in $ℝ{\mathbb{P}}^2$ corresponds to unique point lying on it (vice versa), let this map be $f$, we have

$$I_{max}(𝒮,𝔏)=I_{max}(f^{-1}(𝔏),f(𝒮))=I_{max}(p(f^{-1}(𝔏)),p(f(𝒮)))$$

If we assume $I_{max}(𝔏,𝒮)=g(S,L)$, then we have $I_{max}(p(f^{-1}(𝔏)),p(f(𝒮)))=g(L,S)$, which means $I_{max}(𝔏,𝒮)$ is symmetric for $S$ and $L$. ∎

Solution 7.9.

Firstly, it’s trivial that there doesn’t exist a component with only one side. If there exist a component $K$ with two sides, assuming they’re ${\mathrm{\ell }}_1,{\mathrm{\ell }}_2$ and $P={\mathrm{\ell }}_1\cap {\mathrm{\ell }}_2$, then consider ${\mathrm{\ell }}_3$ that intersects ${\mathrm{\ell }}_1$ and ${\mathrm{\ell }}_2$ at points other than $P$. Such a line ${\mathrm{\ell }}_3$ must exist, because if not, then every line passes $P$. Notice that ${\mathrm{\ell }}_3$ intersects area $K$, we know $K$ isn’t connected, which leads a contradiction.

Let $V_k$ be the number of vertices on exactly $k$ lines and $F_k$ be the number of faces with exactly $k$ sides. Notice that $2E={\sum }_{k=3}^{\mathrm{\infty }}k{F}_k\ge 3F$ and $E={\sum }_{k=2}^{\mathrm{\infty }}k{V}_k$, if $V_2=0$, we have $E\ge 3V_k$. Now

$$V-E+F\le V-E+\frac{2}{3}E=V-\frac{1}{3}E\le V-\frac{1}{3}(3V)=0$$

but we know $V-E+F=1>0$ by Euler’s formula. So that leads a contradiction, which means $V_2\ge 1$.

Using the map $f$ in the previous question, we can get the claim quickly:

Claim. Suppose that $𝒮$ is a finite set of points in $ℝ{\mathbb{P}}^2$, not all lying on one line. Then, there is a line that contains exactly two points of $𝒮$.

Just use the conclusion above for $f^{-1}(𝒮)$, we know there exist a point $v$ on exactly two lines ${\mathrm{\ell }}_{v1}$ and ${\mathrm{\ell }}_{v2}$. Then line $f(v)$ contains exact two points $f({\mathrm{\ell }}_{v1})$ and $f({\mathrm{\ell }}_{v2})$. The claim is true for $ℝ{\mathbb{P}}^2$, so the claim is of course true for ${ℝ}^2$. ∎

Solution 7.10.

Because the $v_i$ are chosen generically, the values of $v_i+v_j(i\ne j)$ and values of $v_i+v_j+v_k(i\ne j,j\ne k,k\ne i)$ are all distinct. So the number of points in $X$ is $N=\left(\genfrac{}{}{0pt}{}{m}{2}\right)\sim m^2$. Let $C_{ij}$ denote the unit circle centered at $v_i+v_j$. Then every point with form $v_i+v_j+v_k$ is on circle $C_{ij},C_{C_{jk}},C_{ki}\in \mathrm{\Gamma }$, which implies $v_i+v_j+v_k$ is 3-rich. Thus the number of 3-rich point of $\mathrm{\Gamma }$ is at least $\left(\genfrac{}{}{0pt}{}{m}{3}\right)\sim m^3\sim N^{\frac{3}{2}}$. ∎

Solution 7.11.

For every point $(x_0,y_0)$ such that $\frac{1}{x_0}\in A$ and $-y_0\in A$, it lies on $y=(x_0\cdot a)x-(a+y_0)$ for every $a\in A$. So $(x_0,y_0)$ is a $r$ -rich point and $P_r(𝔏)\ge {|A|}^2$. By Theorem 7.1, we know

	${|A|}^2$	$\lesssim |A+A|\cdot |A\cdot A|\cdot {|A|}^{-1}+{|A+A|}^2\cdot {|A\cdot A|}^2\cdot {|A|}^{-3}$
		$=|A+A|\cdot |A\cdot A|\cdot {|A|}^2\cdot {|A|}^{-3}+{|A+A|}^{-2}\cdot {|A\cdot A|}^{-2}\cdot {|A|}^{-3}$
		$\le 2{|A+A|}^2\cdot {|A\cdot A|}^2\cdot {|A|}^{-3}$

then we have $|A+A|\cdot |A\cdot A|\gtrsim {|A|}^{\frac{5}{2}}$, which means $\max (|A+A|,|A\cdot A|)\gtrsim {|A|}^{\frac{5}{4}}$.

Regarding of the case $\max (|A-A|,|A/A|)$, let ${𝔏}^{\prime }$ be the set of lines $y=nx-c$ with $n\in A/A$ and $c\in A-A$. For every point $(x_0,y_0)$ such that $x_0\in A$ and $y_0\in A$, it lies on $y=\frac{a}{x_0}x-(a-y_0)$ for every $a\in A$. So $(x_0,y_0)$ is a $r$ -rich point and $P_r({𝔏}^{\prime })\ge {|A|}^2$. By Theorem 7.1, we know

	${|A|}^2$	$\lesssim |A-A|\cdot |A/A|\cdot {|A|}^{-1}+{|A-A|}^2\cdot {|A/A|}^2\cdot {|A|}^{-3}$
		$=|A-A|\cdot |A/A|\cdot {|A|}^2\cdot {|A|}^{-3}+{|A-A|}^{-2}\cdot {|A/A|}^{-2}\cdot {|A|}^{-3}$
		$\le 2{|A-A|}^2\cdot {|A/A|}^2\cdot {|A|}^{-3}$

then we have $|A-A|\cdot |A/A|\gtrsim {|A|}^{\frac{5}{2}}$, which means $\max (|A-A|,|A/A|)\gtrsim {|A|}^{\frac{5}{4}}$. ∎

Solution 7.12.

Consider the simple graph $H$ corresponding to $G$, which has the same vertices as $G$. Every edge of $G$ (regardless of the number of repetitions) corresponds to a single edge in $H$. Let $E_H$ be the number of edges in $H$. We have $E\le M{E}_H$. Thus there is $E_H\ge \frac{E}{M}\ge \frac{4MV}{M}=4V$. Using Theorem 7.6 and we know $k(H)\ge \frac{1}{64}{E}_H^3{V}^{-2}\ge {\left(\frac{E}{M}\right)}^3{V}^{-2}$. Notice that $k(G)\ge k(H)$, we get $k(G)\ge \frac{1}{64}{E}^3{M}^{-3}{V}^{-2}$. ∎

Solution 7.13.

Let $P$ denote the set of $N$ points. Assuming $|d(P)|=t\le N$, let $P$ be vertices of $G$ and we consider the circles centered at points in $P$ with radii in $d(P)$. The number of circles $C=Nt$. Let the edges of $G$ be the arcs of circles between consecutive points, for the circles containing more than one point. We don’t construct an edge for the circles containing only one point to avoid loops.

Notice that, for every circle with more than one point lying on it, the number of arcs equals to the points. Let $U$ be the circles with only one point. Then $E=N(N-1)-|U|\ge N(N-1)-C=N(N-1-t)$. Because there are up to 99 points on the perpendicular bisector of every two points, the number of parallel edges between two points is at most 198, which means $Mult(G)\le 198$.

Firstly, consider the case of $E\ge 4MV=792N$, we can use Proposition 7.13 and get $k(G)\ge \frac{1}{64}\frac{E^3}{{198}^3{N}^2}$. In addition, there is $k(G)\le 2\left(\genfrac{}{}{0pt}{}{C}{2}\right)\le {(Nt)}^2$. Therefore, we have

$${(Nt)}^2\ge k(G)\ge \frac{1}{64}\frac{E^3}{{198}^3{N}^2}\ge \frac{1}{64}\frac{N^3{(N-1-t)}^3}{{198}^3{N}^2}$$

Assume and $N\ge 2$, then

$$u^2\ge \frac{1}{64}\frac{{(1-\frac{1}{N}-u)}^3}{{198}^3}\ge \frac{{(1-2u)}^3}{64\cdot {198}^3\cdot 2^3}$$

which means

$$\frac{1}{64\cdot {198}^3}{u}^3+\left(1-\frac{1}{128\cdot {198}^3}\right)u^2+\frac{1}{256\cdot {198}^3}u\ge \frac{1}{512\cdot {198}^3}$$

Thus, we have $2u\ge \frac{1}{512\cdot {198}^3}$, that is, $t\ge \frac{1}{7948689408}N$. We call $c$ as $\frac{1}{7948689408}$.

For the case of , we have $792N>N(N-1-t)$, which is equivalent to $t>N-793$. When $N\ge 794$, we know $t>N-793>cN$. When $N\le 793$, because $t\ge 1$, $t\ge cN$ is established. All in all, we have $t\ge \frac{1}{7948689408}N$. ∎

Solution 7.14.

Let $S$ be vertices of $G$ and we consider the unit circles centered at points in $S$. Let the edges of $G$ be the arcs of circles between consecutive points, for the circles containing more than one point. Let $m_c=\{p\in S\mid |p-c|=1\}$ denote the number of points on the unit circle centered at $c\in S$ and $D$ denote the number of unit distances. Then we have $E={\sum }_{c\in S,m_c\ge 2}{m}_c,2D={\sum }_{c\in S}{m}_c$ and $Mult(G)\le 4$. Further, we have

$$D=\frac{{\sum }_{c\in S}{m}_c}{2}=\frac{E+|\{c\in S\mid m_c=1\}|}{2}$$

Because two unit circles intersect in at most two points, we have $k(G)\le 2\left(\genfrac{}{}{0pt}{}{N}{2}\right)\le N^2$. When $E\ge 16N$, we know $\frac{E^3}{4096N^2}\le k(G)\le N^2$, which means $E\le 16N^{\frac{4}{3}}$. So there is $D\le \frac{16N^{\frac{4}{3}}+N}{2}\le \frac{17}{2}{N}^{\frac{4}{3}}$. When , we also have $D\le \frac{E+N}{2}\le \frac{17}{2}N\le \frac{17}{2}{N}^{\frac{4}{3}}$. Thus the conclusion is established. ∎

Solution 7.15.

Use the following method to construct the graph $G$: Let $P=P_r(\mathrm{\Gamma })$ be vertices of $G$. For every curve $\gamma \in \mathrm{\Gamma }$, we can consider $P_{\gamma }=\gamma \cap P$, the set of points on $\gamma$. Let the edges of $G$ be the arcs of curves between consecutive points, for the every curve $\gamma$ with $|P_{\gamma }|\ge 2$.

Assuming that $e_{\gamma }$ is the number of edges in $G$ on $\gamma$ and $m_{\gamma }=|P_{\gamma }|$, for $m_{\gamma }\ge 2$, we know $e_{\gamma }=m_{\gamma }$ if $\gamma$ closed and $e_{\gamma }=m_{\gamma }-1$ if $\gamma$ open. Because any two points lie in at most $s$ curves of $\mathrm{\Gamma }$, we get $Mult(G)\le 2s$.

Notice that every point $p\in P$ is $r$ -rich, we have ${\sum }_{\gamma \in \mathrm{\Gamma }}{m}_{\gamma }={\sum }_{p\in P}\{\gamma :p\in \gamma \}\ge rV$. And notice that $\max (m_{\gamma }-1,0)\le e_{\gamma }\le m_{\gamma }$, we have

$$E=\sum _{\gamma \in \mathrm{\Gamma }}{e}_{\gamma }\ge \sum _{\gamma \in \mathrm{\Gamma }}\max (m_{\gamma }-1,0)\ge \sum _{\gamma \in \mathrm{\Gamma }}(m_{\gamma }-1)=\sum _{\gamma \in \mathrm{\Gamma }}{m}_{\gamma }-L\ge rV-L$$

Because any two curves of $\mathrm{\Gamma }$ intersect in at most $s$ points, we know $k(G)\le s\left(\genfrac{}{}{0pt}{}{L}{2}\right)\le \frac{s{L}^2}{2}$.

If $E\ge 4MV=8sV$, we get $\frac{E^3}{512V^2{s}^3}\le k(G)\le \frac{s{L}^2}{2}$, which means $E\le 2^{\frac{8}{3}}{s}^{\frac{4}{3}}{L}^{\frac{2}{3}}{V}^{\frac{2}{3}}$. By $E\ge rV-L$, we know $rV-L\le 2^{\frac{8}{3}}{s}^{\frac{4}{3}}{L}^{\frac{2}{3}}{V}^{\frac{2}{3}}$. Let $K$ denote $2^{\frac{8}{3}}{s}^{\frac{4}{3}}$. For the case of $rV\ge 2L$, we know $\frac{rV}{2}\le rV-L\le K{L}^{\frac{2}{3}}{V}^{\frac{2}{3}}$, that is,

$$V\le {\left(\frac{2K{L}^{\frac{2}{3}}}{r}\right)}^3=\frac{8K^3{L}^2}{r^3}=2048s^4{L}^2{r}^{-3}$$

For the case of , we have .

If , from $E\ge rV-L$, we know $V(r-8s)\le L$. For the case of $r\ge 16s$, we have $V\le \frac{L}{r-8s}\le \frac{L}{\frac{r}{2}}=2L{r}^{-1}$. For the case of , by $V\le s\left(\genfrac{}{}{0pt}{}{L}{2}\right)\le \frac{s{L}^2}{2}$, we have

$$V\le \frac{s{L}^2}{2}=\frac{s{L}^2}{2}{r}^3{r}^{-3}\le \frac{s{L}^2}{2}{r}^{-3}{(16s)}^3=256s^4{L}^2{r}^{-3}$$

In summary, we get $|P_r(\mathrm{\Gamma })|\le C(s)(L^2{r}^{-3}+L{r}^{-1})$. ∎

Solution 7.16.

⁴⁴ 4 The condition $r\gtrsim N^{\frac{1}{3}}$ in this problem should be $r\sim N^{\frac{1}{3}}$, or we have and .

Consider the set of parabolas $\mathrm{\Gamma }=\{x^2+ax+b\mid a=0,1,\mathrm{\cdots },k-1,b=0,1,\mathrm{\cdots },k^2-1\}$ with $|\mathrm{\Gamma }|=N=k^3$ and set of points $S=\{(m,n)\mid 0\le m\le k+1,n=0,1,\mathrm{\cdots },k^2-1-m(k-1)\}\cup \{(m,n)\mid -k-1\le m\le -1,n=-m(k-1),-m(k-1)+1,\mathrm{\cdots },k^2-1\}$ with $|S|=k^3+k^2+k+2\ge N$ and $|S|\sim N$. Because every $(m,n)\in S$ satisfies $n=m^2+am+b$ for $(a,b)=(0,n-m^2),(1,n-m^2-m),\mathrm{\cdots },(k-1,n-m^2-(k-1)m)$, we know every point in $S$ is $r$ -rich point, with $r=k\sim N^{\frac{1}{3}}$. So the conclusion is established. ∎

Solution 7.17.

Firstly, we will show this conclusion.

Claim. Curve ${\gamma }_0$ intersects ${\gamma }_0+v$ in at most 2 points, assuming $v\ne 0$.

WLOG, we can assume that $v=(0,m)$ with $m>0$. Choose $a$ and $b$ as the left and right endpoint of ${\gamma }_0$ (that is, the points on ${\gamma }_0$ with the smallest and largest $x$ coordinate). Let $f_u(x)=\max \{y\mid (x,y)\in {\gamma }_0\}$ and $f_l(x)=\min \{y\mid (x,y)\in {\gamma }_0\}$. Then we have ${\gamma }_0=\{(x,f_u(x))\mid x\in [a,b]\}\cup \{(x,f_l(x))\mid x\in [a,b]\}$ and ${\gamma }_0+v=\{(x,f_u(x)+m)\mid x\in [a,b]\}\cup \{(x,f_l(x)+m)\mid x\in [a,b]\}$. ⁵⁵ 5 This part of the proof comes from [5].Since $m>0$, graphs of $f_u$ and $f_u+m$ are disjoint, the graphs of $f_l,f_l+m$ are disjoint and the graphs of $f_l,f_u+m$ are also disjoint. Only the graphs of $f_l+m$ and $f_u$ can intersect. Then, the conclusion reduces to the claim that the graph of a strictly convex function $h_1$ can intersect the graph of a strictly concave function $h_2$ in at most two points. Notice that $h_1-h_2$ is strictly convex, we know it has at most 2 roots, so the claim is established.

If there are 3 curves ${\gamma }_0,{\gamma }_0+t,{\gamma }_0+s$ all passing $p,q$, then ${\gamma }_0$ passes $p,p-t,p-s$ and $q,q-t,q-s$. That means ${\gamma }_0$ intersects ${\gamma }_0+(q-p)$ at 3 points, which leads a contradiction. So any two points in the plane lie in at most two of the curves of $\mathrm{\Gamma }$.

Now applying Theorem 7.16, we know $|P_r(\mathrm{\Gamma })|\lesssim {|\mathrm{\Gamma }|}^2{r}^{-3}+|\mathrm{\Gamma }|r^{-1}$. Suppose that ${\gamma }_0$ has diameter of $d$, assuming $d\ge 1$, we choose a $10d\times 10d$ square $B$ such that ${\gamma }_0\subseteq \overline{B}$. We call ${\mathrm{\Gamma }}_B$ as $\{{\gamma }_0+v\mid v\in {\mathbb{Z}}^2,({\gamma }_0+v)\cap \overline{B}\ne 0\}$ and $r(p)$ as the number of curves in $\mathrm{\Gamma }$ passing $p$, assuming $\mathrm{\Gamma }=\{{\gamma }_0+v\mid v\in {ℝ}^2\}$. Consider $𝒫=\overline{B}\cap {\mathbb{Z}}^2$ and $S={\gamma }_0\cap {\mathbb{Z}}^2$ with $|S|=n$, we know for every point $p\in 𝒫$,

$$r(p)=|\{v\in {\mathbb{Z}}^2\mid p-v\in {\gamma }_0\}|=|\{s\in {\gamma }_0\mid s=p-v\text{ for some }v\in {\mathbb{Z}}^2\}|=|S|=n$$

which means every $p$ is contained by $n$ curves in ${\mathrm{\Gamma }}_B$. Notice that $|{\mathrm{\Gamma }}_B|\le k{d}^2$ and $|𝒫|\ge c{d}^2$, we know

$$c{d}^2\le |𝒫|\le |P_n(\mathrm{\Gamma })|\le {|{\mathrm{\Gamma }}_B|}^2{n}^{-3}+|{\mathrm{\Gamma }}_B|n^{-1}=k^2{d}^4{n}^{-3}+k{d}^2{n}^{-1}$$

by the inequality above. So we have $c\le k^2{d}^2{n}^{-3}+k{n}^{-1}$.

For the case of $k^2{d}^2{n}^{-3}\ge k{n}^{-1}$, we know $n\le {\left(\frac{2k^2}{c}\right)}^{\frac{1}{3}}{d}^{\frac{2}{3}}$ because $c\le k^2{d}^2{n}^{-3}+k{n}^{-1}\le 2k^2{d}^2{n}^{-3}$. For the case of $k^2{d}^2{n}^{-3}\le k{n}^{-1}$, we have $c\le k^2{d}^2{n}^{-3}+k{n}^{-1}\le 2k{n}^{-1}$, so there is $n\le \frac{2k}{c}\le \frac{2k}{c}{d}^{\frac{2}{3}}$. Anyway, the conclusion is established. ∎

Solution 7.18.

We’ll prove this claim firstly.

Claim. For every $G$ with $E>2^{2-i}MV$ satisfying that between any two vertices of $G$, the number of edges is either $0$ or lies in $[\frac{M}{2^{i+1}},\frac{M}{2^i}]$, its crossing number $k(G)\ge 2^{i-8}{E}^3{V}^{-2}{M}^{-1}$.

Consider the simple graph $H$ corresponding to $G$, we have $\frac{2^{i}E}{M}\le E_H\le \frac{2^{i+1}E}{M}$, which implies $E_H>\frac{2^{2-i}{2}^{i}MV}{M}=4V$. Take a random subgraph $G^{\prime }\subseteq G$ consisting of one edge between each pair of vertices. In the induced embedding on the subgraph, each crossing occurs with probability $\le {\left(\frac{2^{i+1}}{M}\right)}^2$, since it occurs if and only if both edges are in $G^{\prime }$. Now we have $𝔼(k(G^{\prime }))\le \frac{2^{2i+2}}{M^2}k(G)$, that is,

$$k(G)\ge 2^{-2i-2}{M}^2𝔼(k(G^{\prime }))\ge \frac{1}{64\cdot 2^{2i+2}}{M}^2{E}_H^3{V}^{-2}\ge 2^{i-8}{E}^3{V}^{-2}{M}^{-1}$$

since $E_{G^{\prime }}=E_H>4V$ and $E_H\ge \frac{2^{i}E}{M}$.

⁶⁶ 6 This idea comes from [9].

For $0\le i\le [{\log }_{2}m]$, let $G_i$ be the subgraph of $G$, satisfying that between any two vertices of $G_i$, the number of edges is either $0$ or lies in $[2^i,2^{i+1})$. Define $A=\{i\mid E_{G_i}\le 2^{i+3}V\}$ and $B=\{0,1,\mathrm{\cdots },{\log }_{2}M\}\backslash A$, from ${\sum }_{i\in A}{E}_{G_i}\le 2\cdot 2^{[{\log }_{2}M]+3}\le 16MV$, we know

$$\sum _{i\in B}{E}_{G_i}=E-\sum _{i\in A}{E}_{G_i}\ge E-16MV\ge \frac{E}{2}$$

Notice that

$$k(G)\ge \sum _{i=0}^{[{\log }_{2}m]}k(G_i)\ge \sum _{i\in B}k(G_i)\ge 2^{-8}{V}^{-2}{M}^{-1}\sum _{i\in B}{2}^i{E}_{G_i}^3$$

by Holder inequality, we know

$$\sum _{i\in B}{2}^i{E}_{G_i}^3=\sum _{i\in B}\frac{E_{G_i}^3}{2^{-i}}\ge \frac{{\left({\sum }_{i\in B}{E}_{G_i}\right)}^3}{{\left({\sum }_{i\in B}{2}^{-\frac{i}{2}}\right)}^2}\ge {\left(\frac{E}{2}\right)}^3$$

so we have $k(G)\ge 2^{-11}{E}^3{V}^{-2}{M}^{-1}=\frac{1}{2048}{E}^3{V}^{-2}{M}^{-1}$. ∎

Solution 7.19.

We let $k_C$ be the number of points on circle $C\in \mathrm{\Gamma }$. Let $f_p$ denote the number of circles containing point $p$. Now we know

$$E=\sum _{C\in \mathrm{\Gamma }}{k}_C=\sum _{p\in S}{f}_p$$

Let $g_p$ be the number of circles in ${\mathrm{\Gamma }}_0\backslash \mathrm{\Gamma }$, only containing $p$ and $s_q$ be the number of circles in ${\mathrm{\Gamma }}_0\backslash \mathrm{\Gamma }$, centered at $q$. Notice ${\sum }_{p\in S}{g}_p={\sum }_{q\in S}{s}_q\le {\sum }_{q\in S}t=Nt$, we have

$$\sum _{q\in S}{s}_q\le \sum _{q\in S}t=Nt\le \frac{1}{100}{N}^2$$

So

$$E=\sum _{p\in S}{f}_p=\sum _{p\in S}(N-1-g_p)=N(N-1)-\sum _{q\in S}{g}_q\ge N(N-1)-\frac{1}{100}{N}^2\ge \frac{1}{2}{N}^2$$

for $N\ge 3$. ∎

Solution 7.20.

⁷⁷ 7 Besides hint, this idea also comes from [9].

We assume $t\le c{N}^{\frac{4}{5}}$, otherwise we have $t\gtrsim N^{\frac{4}{5}}$ trivially. By Lemma 7.19, the number of edges of $G$ with multiplicity at least $M$ is at most $C[N^2{M}^{-2}t+N\log Nt]$. We take $M=\sqrt{12Ct}$, then the value above changed into $\frac{N^2}{12}+CN\log Nt$. Using the bound $t\le c{N}^{\frac{4}{5}}$, we know

	$E_{\ge M}$	$\ge E_G-\left({\displaystyle \frac{N^2}{12}}+CN\log Nt\right)\ge {\displaystyle \frac{1}{2}}{N}^2-\left({\displaystyle \frac{N^2}{12}}+CN\log Nt\right)$
		$={\displaystyle \frac{5}{12}}{N}^2-CN\log Nt\ge {\displaystyle \frac{5}{12}}{N}^2-CN\log c{N}^{\frac{9}{5}}=\ge {\displaystyle \frac{N^2}{3}}$

when $N$ sufficient large. Therefore we have $E_{\le M}\ge \frac{N^2}{3}\ge 100\sqrt{12C}{N}^{\frac{7}{5}}=100MV$ when $N$ sufficient large. Now apply Theorem 7.17 on $G_{\le M}$ and we know

$$k(G_{\le M})\ge c_0{E}_{\le M}^3{V}^{-2}{M}^{-1}\ge c_0{\left(\frac{N^2}{3}\right)}^3{N}^{-2}{M}^{-1}=\frac{c_0}{27}{N}^4{M}^{-1}$$

Using $k(G_{\le M})\le k(G)\le 2{(Nt)}^2$, we know

$$2N^2{t}^2\ge \frac{c_0}{27}{N}^4{M}^{-1}=\frac{c_0}{27}{N}^4{\left(\sqrt{12Ct}\right)}^{-1}=\frac{c_0}{27\sqrt{12Ct}}{N}^4$$

Thus we have $t\ge {\left(\frac{c_0}{54\sqrt{12C}}\right)}^{\frac{2}{5}}{N}^{\frac{4}{5}}$, which means $t\sim N^{\frac{4}{5}}$. That is, we have $t\gtrsim N^{\frac{4}{5}}$. ∎

Solution 8.1.

⁸⁸ 8 Hint of this problem may has defect. This solution has fixed that.

For any point $x=(x_1,x_2,x_3)\in {ℝ}^3$, with $x\ne 0,1$, we define a map ${\rho }_x:{ℝ}^2\to {ℝ}^2$ as follows. If $v\in {ℝ}^2$, then we define ${\rho }_x(v)$ so that $(v,0)$, $x$ and $({\rho }_x(v),1)$ are collinear. Now observe that $x$ is $r$ -rich if and only if $|{\rho }_x(G_0)\cap G_1|\ge r$. Construct a vertical line $\mathrm{\ell }$ perpendicular to plane $x_3=0$ through point $x$, assume $\mathrm{\ell }$ intersects $x_3=0$ and $x_3=1$ at $h_0,h_1$ respectively. We can get $\mathrm{△}x{h}_0(v,0)$ is similar to $\mathrm{△}x{h}_1({\rho }_x(v),1)$, which means $p_x(v_1,v_2)=-\frac{1-x_3}{x_3}v+\frac{1}{x_3}(x_1,x_2)$. Let $k=-\frac{1-x_3}{x_3}$ and $t=\frac{1}{x_3}$, we have ${\rho }_x(v)=kv+tx$. We let $f_k(x)=|\{a\in \{1,2,\mathrm{\cdots },N\}\mid ka+tx\in \{1,2,\mathrm{\cdots },N\}\}|$, where $N=L^{\frac{1}{4}}\ge 20$, then $x$ is $r$ -rich if and only if $f_k(x_1)f_k(x_2)\ge r$. Let’s consider $k=\frac{q-d}{q}$, where $q,d$ are both positive integers satisfying $\gcd (q,d)=1$ and . Now $x_3=\frac{q}{d},t=\frac{d}{q}$ and $k=1-\frac{d}{q}$.

Claim. Assuming $N\ge 2q$, then for $k=\frac{q-d}{q}$, the number of $x$ satisfying $f_k(x)\ge \frac{N}{2q}$ is at least $Nq$.

For $x=\frac{1}{d},\frac{2}{d},\mathrm{\cdots },\frac{Nq}{d}$, we know $\frac{q-d}{q}\cdot (-{(q-d)}^{-1}dx+mq)+\frac{d}{q}x\in \{1,2,\mathrm{\cdots },N\}$, for $m=0,1,\mathrm{\cdots },\left[\frac{N}{q}\right]-1$, where ${(q-d)}^{-1}$ is the number-theoretic inverse of $q-d$ modulo $q$. Notice $m$ can take $\left[\frac{N}{q}\right]\ge \frac{N}{2q}$ values, we know the claim is established.

When $r$ is fixed, let $Q=\lceil \frac{N}{4\sqrt{r}}\rceil$. For every $(q,d)$ pair, which satisfies and $q\le Q$, contribute ${(Nq)}^2$ choices for $(x_1,x_2)$ pairs. (Because $2\le r\le \frac{N^2}{400}$, we know $q\le Q\le \frac{N}{2\sqrt{r}}$, which means $N\ge 2\sqrt{r}q\ge 2q$, we can use the claim above.) And for every fixed $q$, there are $2\phi (q)$ choices of $d$, for $\gcd (q,d)=1$ and . Now the number of lines passing $x$ is $f_k(x_1)f_k(x_2)\ge {\left(\frac{N}{2q}\right)}^2\ge {\left(\frac{N}{2Q}\right)}^2\ge r$.

Then we know

	$|P_r(𝔏)|$	$\ge {\displaystyle \sum _{q=1}^Q}2\phi (q)N^2{q}^2=2N^2{\displaystyle \sum _{q=1}^Q}\phi (q)q^2\ge 2N^2{\displaystyle \sum _{1\le q\le Q,q\text{ odd}}}{\displaystyle \frac{1+q}{2}}{q}^2$
		$\ge {\displaystyle \frac{N^{2}Q(Q+2)(3Q^2-2Q-2)}{24}}\ge {\displaystyle \frac{N^2{Q}^4}{12}}\ge {\displaystyle \frac{1}{12}}{\displaystyle \frac{L^{\frac{3}{2}}}{r^2}}\gtrsim L^{\frac{3}{2}}{r}^{-2}$

when $Q\ge 3$. Since $Q\ge \frac{N}{4\sqrt{r}}=\sqrt{\frac{N^2}{16r}}\ge 5$, we know the inequality above is true. ∎

Solution 8.2.

Step 1: For every $y\in S(u,r)\cap S(v,r)$, it satisfies ${\sum }_{i=1}^3{(u_i-y_i)}^2=r$ and ${\sum }_{i=1}^3{(v_i-y_i)}^2=r$. Then we know

$$0=\sum _{i=1}^3{(u_i-y_i)}^2-{(v_i-y_i)}^2=\sum _{i=1}^3(u_i^2-v_i^2+2y_i{v}_i-2y_i{u}_i)=\sum _{i=1}^3(u_i^2-v_i^2)-2y_i(u_i-v_i)$$

which means ${\sum }_{i=1}^3(u_i-v_i)y_i={\sum }_{i=1}^3(u_i-v_i)2^{-1}(u_i+v_i)$.

Step 2: If $\mathrm{Perp}(u,v)=\mathrm{Perp}(u,w)$, we know there exist $c\ne 0$ satisfying $u_i-v_i=c(u_i-w_i)$ for $i=1,2,3$ and ${\sum }_{i=1}^3(u_i-v_i)2^{-1}(u_i+v_i)=c\left({\sum }_{i=1}^3(u_i-w_i)2^{-1}(u_i+w_i)\right)$.

Step 3: Notice that $S(u,r)\cap S(v,r)\cap S(w,r)\subseteq \mathrm{Perp}(u,v),\mathrm{Perp}(v,w)$ and $\mathrm{Perp}(w,u)$, thus $S(u,r)\cap S(v,r)\cap S(w,r)\subseteq \mathrm{Perp}(u,v)\cap \mathrm{Perp}(v,w)\cap \mathrm{Perp}(w,u)$. We can know $\mathrm{Perp}(u,v)\cap \mathrm{Perp}(v,w)\cap \mathrm{Perp}(w,u)$ is a line from the equation of plane. We call this line as $\mathrm{\ell }$.

Step 4: From $S(0,r)$ doesn’t contain any line, we know $S(u,r)$ also doesn’t contain any line. Since $S(u,r)\cap S(v,r)\cap S(w,r)\subseteq \mathrm{\ell }\cap S(u,r)$, we consider the points in $|\mathrm{\ell }\cap S(u,r)|$. It can be realized as finding roots of a quadratic equation whose coefficients are not all 0. (Specifically, we substitute $\mathrm{\ell }:y=at+b$ into the equation $S(u,r)$ to solve for $t$.) Thus we know $|\mathrm{\ell }\cap S(u,r)|\le 2$, which leads the conclusion.

Step 5: Suppose that $S(0,r)$ contains the line parametrized by $\gamma (t)=\overrightarrow{m}t+\overrightarrow{b}$, where $\overrightarrow{m}=(m_1,m_2,m_3)$ and $\overrightarrow{b}=(b_1,b_2,b_3)$. This is equivalent to saying that ${\sum }_{i=1}^3{(m_{i}t+b_i)}^2-r=0$ for all $t\in {𝔽}_q^3$. If we expand the left-hand side as a polynomial in $t$, each coefficient must vanish, leading to the equations

$$\sum _{i=1}^3{m}_i^3=0;\sum _{i=1}^3{m}_i{b}_i=0;\sum _{i=1}^3{b}_i^2=r$$

These formulas lead to a tricky way of writing $r$ as a negative square. Since $-1$ is a quadratic residue, we can conclude that $r$ is a quadratic residue.

	$m_1^{2}r$	$=m_1^2(b_1^2+b_2^2+b_3^2)={(m_1{b}_1)}^2+m_1^2(b_2^2+b_3^2)$
		$={(m_2{b}_2+m_3{b}_3)}^2-(m_2^2+m_3^2)(b_2^2+b_3^2)=-{(m_2{b}_3-m_3{b}_2)}^2$

If $m_1=0$, we can know $r=b_1^2$ by calculation. So the conclusion is established.

Step 6: If $r_1,r_2$ are any two quadratic non-residues, we have

$$\chi (r_2{r}_1^{-1})=\chi (r_2)\chi (r_1^{-1})=(-1)(-1)=1$$

which means $r_2{r}_1^{-1}$ is a quadratic residue. So there exists $k\in {𝔽}_q^{\ast }$ such that $k^2=r_2{r}_1^{-1}$. Consider bijection $\phi (y)=ky$, it maps the element in $S(0,r_1)$ to $S(0,r_2)$ since for every $y\in S(0,r_1)$, we have

$${\Vert \phi (y)\Vert }^2={(k{y}_1)}^2+{(k{y}_2)}^2+{(k{y}_3)}^2=k^2(y_1^2+y_2^2+y_3^2)=k^2{r}_1=r_2$$

Therefore we have $|S(0,r_1)|=|S(0,r_2)|$.

If $r_1,r_2$ are both non-zero quadratic residues, assuming $r_1=a^2$ and $r_2=b^2$, we can consider bijection $\phi (y)=b{a}^{-1}y$. Then we know $|S(0,r_1)|=|S(0,r_2)|$ similarly.

For the case of $r=0$, we consider the equation of $y_1^2+y_2^2=-y_3^2$. Using the formula in [6]:

$$N(c)=q-\chi (-1)\text{ for }c\ne 0\text{and}N(0)=q+\chi (-1)(q-1)$$

where $N(c)$ represents the number of roots of $u^2+v^2=c$ in ${𝔽}_q$. If $y_3=0$, we have $N(0)=2q-1$. If $y_3\ne 0$, we have $N(-y_3^2)=q-1$. Adding them up and we get $|S(0,0)|=2q-1+(q-1)(q-1)=q^2$.

For the case of $r=s^2\ne 0$, we consider the equation of $y_1^2+y_2^2=s^2-y_3^2$. If $y_3=\pm s$, we know $N(0)=2q-1$. If $y_3\ne \pm s$, we know $N(s^2-y_3^2)=q-1$. Adding them up and we get $|S(0,s^2)|=2(2q-1)+(q-2)(q-1)=q^2+q$.

For the case of $r$ is quadratic non-residue, we consider the equation of $y_1^2+y_2^2=r-y_3^2$. For every $y_3$, we have $r-y_3^2\ne 0$. Since $N(r-y_3^2)=q-1$, we know $|S(0,r)|=q(q-1)=q^2-q$. ∎

Solution 8.3.

Consider the equation of quadratic surface: $Q(x)=x^{\top }Ax+b^{\top }x+c=0$, where $A$ is a symmetric matrix and $b$ is a vector. Since the scalar equivalence, we know its degrees of freedom can be realized as a 9-dimension projective space. Every line $l_i$ can be parameterized as $r_i(t)=p_i+t{d}_i$. So $Q(p_i+t{d}_i)=0$ for $i=1,2,3$ and every $t$, which means the coefficients of a quadratic polynomial in $t$ are all 0. That is, for $i=1,2,3$ and every $t$,

$$d_i^{\top }A{d}_i=0,2p_i^{\top }A{p}_i+b^{\top }{d}_i=0,p_i^{\top }A{p}_i+b^{\top }{p}_i+c=0$$

There are 9 linear equations. Then the dimension of solution is 0, in the sense of scalar equivalence. So there is only one degree 2 algebraic surface containing the three lines. ∎

Solution 8.4.

About the smoothness of $R(l_1,l_2,l_3)$, we consider the singularity $p$ such that $Q(p)=0$ and $\nabla Q(p)=2Ap+b=0$. Assuming $\mathrm{\ell }:r(t)=pt+d$ is a line passing $p$, since the two conditions above, we have

$$Q(p+td)={(p+td)}^{\top }A(p+td)+b^{\top }(p+td)+c=t^2(d^{\top }Ad)$$

Let $d=q-p$, here $q\in R(l_1,l_2,l_3)$, we know $d^{\top }Ad=0$, which means the line passing $p,q$ is on $R(l_1,l_2,l_3)$. Since the conclusion above is established for any $q\in R(l_1,l_2,l_3)$, we know $R(l_1,l_2,l_3)$ is a conical surface with vertex $p$. Then $l_1,l_2,l_3$ won’t be skew because they all passes $p$, which leads a contradiction.

For any point $p\in R(l_1,l_2,l_3)$, assume that line $r(t)=p+td$ passes it. Using Taylor expansion, we know $Q(p+td)=Q(p)+t\nabla Q(p)\cdot d+t^2{d}^{\top }Ad=t(\nabla Q(p)\cdot d+)t^2(d^{\top }Ad)$. Now we have $\nabla Q(p)\cdot d=0$ and $d^{\top }Ad=0$. Equation $\nabla Q(p)\cdot d=0$ shows $d$ is on tangent plane passing $p$. Notice that reguli are irreducible, we know $d^{\top }Ad$ is not always 0 in that tangent plane. (Otherwise, any $d\ne 0$ will match the condition above, which means $R(l_1,l_2,l_3)$ vanish in that tangent plane, leading that $R(l_1,l_2,l_3)$ is reducible.) Since $d^{\top }Ad$ is quadratic, it has at most two linear factors. That is, there are at most two lines satisfy the condition above.

For other fields, the conclusions are also true. For $𝔽\ne {𝔽}_{2^n}$, the proof above also works.. When $𝔽={𝔽}_{2^n}$, the proof should be modified a bit.

Regarding of the smoothness, if there is a singularity, we know $b=0$. Choose $p,q\in R(l_1,l_2,l_3)$, we have $p^{\top }Ap+c=0$ and $q^{\top }Aq+c=0$. Let $r(t)=p+t(q-p)$, then

$$Q(r(t))={(p+t(q-p))}^{\top }A(p+t(q-p))+c$$

Expand it and use $p^{\top }Aq=q^{\top }Ap$ and $2=0$ to simplify, we have $Q(r(t))=0$, which means $r(t)\in R(l_1,l_2,l_3)$. Because it is established for any $p,q$, we know $R(l_1,l_2,l_3)$ contains a plane, which is contradictory to that $R(l_1,l_2,l_3)$ is irreducible.

Regarding that there are at most two lines in $R(l_1,l_2,l_3)$ passing one point, just expand $Q(p+td)={(p+td)}^{\top }A(p+td)+b^{\top }(p+td)+c$ and simplify. We can get $Q(p+td)=t(b^{\top }d)+t^2(d^{\top }Ad)$, which means $b^{\top }d=0$ and $d^{\top }Ad=0$ if $r(t)=p+td\in R(l_1,l_2,l_3)$ for any $t$. And that’s contradictory to that $R(l_1,l_2,l_3)$ is irreducible. ∎

Solution 8.5.

With a similar proof of Theorem 8.18, we can know:

Claim. Suppose that $𝔏$ is a set of $L$ lines in ${𝔽}^3$ with $\le B$ lines in any plane or degree 2 surface. Then the number of intersection points of $𝔏$ is $\le K{B}^{\frac{1}{3}}{L}^{\frac{5}{3}}$, where $K\ge 1$ is constant .

Just replace all ”10” of the proof of Theorem 8.18 with ”$B$”, we can finish proof of the claim above.

We will prove by induction that a set of $L$ lines determines at most $C{L}^{\frac{7}{4}}$ joints. More precisely, here $C=K^{\frac{3}{4}}{2}^{\frac{1}{4}}$.

Take $B=K^{-\frac{3}{4}}{2}^{\frac{3}{4}}{L}^{\frac{1}{4}}$, let $\beta =K^{-\frac{3}{4}}{2}^{\frac{3}{4}}$, now $B=\beta L^{\frac{1}{4}}$. If $L=3$, we have $J(𝔏)\le 1$ and $K^{\frac{3}{4}}{2}^{\frac{1}{4}}{L}^{\frac{7}{4}}\ge 1$. So the inductive foundation is established. We can assume that, for any ${𝔏}^{\prime }$ containing lines, we have $J({𝔏}^{\prime })\le C{(L^{\prime })}^{\frac{7}{4}}$. Now consider the line set $𝔏$ with $L$ lines.

For the case that there is no plane or regulus containing more than $B$ lines, consider the number of intersections, we have $J(𝔏)\le K{B}^{\frac{1}{3}}{L}^{\frac{5}{3}}=K{\beta }^{\frac{1}{3}}{L}^{\frac{7}{4}}=C{L}^{\frac{7}{4}}$.

If there exist a plane or regulus containing more than $B$ lines, we call it $\mathrm{\Sigma }$ and let ${𝔏}_{\mathrm{\Sigma }}\subseteq 𝔏$ denote the lines in $\mathrm{\Sigma }$. Notice that $|{𝔏}_{\mathrm{\Sigma }}|>B$, let ${𝔏}^{\prime }=𝔏\backslash {𝔏}_{\mathrm{\Sigma }}$ and we have . If $\mathrm{\Sigma }$ is plane, any three lines are coplanar,then there doesn’t exist joint on $\mathrm{\Sigma }$. If $\mathrm{\Sigma }$ is regulus, any point lies on at most two lines, then there doesn’t exist joint on it. So there’s no joint in ${𝔏}_{\mathrm{\Sigma }}$.

The joints in $𝔏$ can be divided into two categories. In the first category, the three lines that make up the joints are all in $𝔏$, the number of these joints is $J(𝔏)$. In the second category, those three lines have at least one in $\mathrm{\Sigma }$ and at least one in ${𝔏}^{\prime }$. For this category, every line in ${𝔏}^{\prime }$ intersects $\mathrm{\Sigma }$ at most 2 points. So the number of joints in the second category is at most $2|{𝔏}^{\prime }|\le 2L$. Now we have

$$J(𝔏)\le |J({𝔏}^{\prime })|+2L\le C{(L-B)}^{\frac{7}{4}}+2L\le C{L}^{\frac{7}{4}}$$

The last inequality holds when $L\ge 3$ and $K\ge 1$, here we omit some of the calculation details. So the induction finishes and conclusion is established. ∎

Solution 10.1.

Let $D$ be a degree that we will choose later. By Theorem 10.3, we can find a non-zero polynomial $P$ of degree $\le D$ so that each component of the complement of $Z(P)$ contains $\lesssim S{D}^{-2}$ points of $𝒮$. Let $O_i$ be the components of ${ℝ}^2\backslash Z(P)$. For each $i$, let ${𝒮}_i=𝒮\cap O_i$ and let ${\mathrm{\Gamma }}_i\subseteq \mathrm{\Gamma }$ be the set of unit circles of $\mathrm{\Gamma }$ that intersect $O_i$. Let $S_i=|{𝒮}_i|$ and $N_i=|{\mathrm{\Gamma }}_i|$. Since circle is a quadratic curve, if it isn’t contained in $Z(P)$, then it intersects $Z(P)$ in at most $2D$ points, by Bezout Theorem. Thus every unit circle passes $\lesssim D$ cells, which means ${\sum }_i{N}_i\lesssim ND$.

Claim. If $𝒮$ is a set of $S$ points in ${ℝ}^2$, and $\mathrm{\Gamma }$ is a set of $N$ unit circles in ${ℝ}^2$, then
(1) $I(𝒮,\mathrm{\Gamma })\le N+2S^2$;
(2) $I(𝒮,\mathrm{\Gamma })\le 2N^2+S$.

Fix $x\in 𝒮$. Let $N_x$ be the number of circles of $\mathrm{\Gamma }$ that contain $x$ and no other point of $𝒮$. For each other point $y\in S$, there is at most two circles of $\mathrm{\Gamma }$ containing $x$ and $y$. Therefore, $I(x,\mathrm{\Gamma })\le 2S+N_x$. So $I(𝒮,\mathrm{\Gamma })\le 2S^2+{\sum }_{x\in 𝒮}{N}_x\le 2S^2+N$. The proof of the other inequality is similar.

If $N>S^2$ or $S>N^2$, then the conclusion follows from the claim above. Therefore, we can now restrict to the case that $S^{\frac{1}{2}}\le N\le S^2$.

Applying the claim in each cell, we get $I({𝒮}_i,{\mathrm{\Gamma }}_i)\le N_i+2S_i^2$ then

$$I({𝒮}_{cell},\mathrm{\Gamma })=\sum _{i}I({𝒮}_i,{\mathrm{\Gamma }}_i)\lesssim \sum _i{N}_i+\sum _i{S}_i^2\lesssim ND+S{D}^{-2}\sum _i{S}_i\le ND+S^2{D}^{-2}$$

Since every circle intersects $Z(P)$ in at most $2D$ points if it isn’t contained in $Z(P)$, we have $I({𝒮}_{alg},{\mathrm{\Gamma }}_{cell})\le 2ND$. Consider the degree, the number of circles in $Z(P)$ is at most $\frac{D}{2}$. Using the claim above, we get $I({𝒮}_{alg},{\mathrm{\Gamma }}_{alg})\le S+\frac{D^2}{2}$.

Adding them up and we know $I(𝒮,\mathrm{\Gamma })\lesssim ND+S^2{D}^{-2}+S+D^2$. Take $D\sim S^{\frac{2}{3}}{N}^{-\frac{1}{3}}$, from $N\le S^2$, we know $S^{\frac{2}{3}}{N}^{-\frac{1}{3}}\ge 1$. Also from $S^{\frac{1}{2}}\le N$, we know $D^2\sim S^{\frac{4}{3}}{N}^{-\frac{2}{3}}\le S$. Therefore, $I(𝒮,\mathrm{\Gamma })\lesssim S^{\frac{2}{3}}{N}^{\frac{2}{3}}+S$. And let $\mathrm{\Gamma }$ be the unit circles centered at $𝒮$, we know $S=N$ and $I(𝒮,\mathrm{\Gamma })\lesssim N^{\frac{4}{3}}$, which means a set of $N$ points in the plane determines $\lesssim N^{\frac{4}{3}}$ unit distances. ∎

Solution 10.2.

⁹⁹ 9 Conclusions needed to prove should be $I(𝒮,\mathrm{\Gamma })\lesssim S^3+N$ and $I(𝒮,\mathrm{\Gamma })\lesssim S^{\frac{3}{5}}{N}^{\frac{4}{5}}+N+S$.

Consider the circumcenter of a triangle, we can know a set of 3 points lies on a unique circle immediately. Fix $x\in 𝒮$. Let ${\mathrm{\Gamma }}_{high}\subseteq \mathrm{\Gamma }$ be the circles containing at least 3 points in $𝒮$ and ${\mathrm{\Gamma }}_{low}=\mathrm{\Gamma }\backslash {\mathrm{\Gamma }}_{high}$. Therefore, $I(x,\mathrm{\Gamma })=I(x,{\mathrm{\Gamma }}_{high})+I(x,{\mathrm{\Gamma }}_{low})\le \left(\genfrac{}{}{0pt}{}{S-1}{2}\right)+I(x,{\mathrm{\Gamma }}_{low})$. So $I(𝒮,\mathrm{\Gamma })\le S\cdot S^2+{\sum }_{x\in 𝒮}I(x,{\mathrm{\Gamma }}_{low})\le S^3+(N+2N)\lesssim S^3+N$.

Let $D$ be a degree that we will choose later. By Theorem 10.3, we can find a non-zero polynomial $P$ of degree $\le D$ so that each component of the complement of $Z(P)$ contains $\lesssim S{D}^{-2}$ points of $𝒮$. Let $O_i$ be the components of ${ℝ}^2\backslash Z(P)$. For each $i$, let ${𝒮}_i=𝒮\cap O_i$ and let ${\mathrm{\Gamma }}_i\subseteq \mathrm{\Gamma }$ be the set of circles of $\mathrm{\Gamma }$ that intersect $O_i$. Let $S_i=|{𝒮}_i|$ and $N_i=|{\mathrm{\Gamma }}_i|$. Since circle is a quadratic curve, if it isn’t contained in $Z(P)$, then it intersects $Z(P)$ in at most $2D$ points, by Bezout Theorem. Thus every circle passes $\lesssim D$ cells, which means ${\sum }_i{N}_i\lesssim ND$.

Applying that in each cell, we get

$$I({𝒮}_{cell},\mathrm{\Gamma })=\sum _{i}I({𝒮}_i,{\mathrm{\Gamma }}_i)\lesssim \sum _i{N}_i+\sum _i{S}_i^3\lesssim ND+{(S{D}^{-2})}^2\sum _i{S}_i\le ND+S^3{D}^{-4}$$

Since every circle intersects $Z(P)$ in at most $2D$ points if it isn’t contained in $Z(P)$, we have $I({𝒮}_{alg},{\mathrm{\Gamma }}_{cell})\le 2ND$. Consider the degree, the number of circles in $Z(P)$ is at most $\frac{D}{2}$.

We can prove $I(𝒮,\mathrm{\Gamma })\le S+2N^2$ by the method in Exercise 10.1. Using the inequality above, we get $I({𝒮}_{alg},{\mathrm{\Gamma }}_{alg})\le S+\frac{D^2}{2}$.

If $N>S^3$ or $S>N^2$, then we know $I(𝒮,\mathrm{\Gamma })\lesssim N$ or $S$ respectively. Therefore, we can now restrict to the case that $S^{\frac{1}{2}}\le N\le S^3$.

Adding them up and we know $I(𝒮,\mathrm{\Gamma })\lesssim ND+S^3{D}^{-4}+S+D^2$. Take $D\sim S^{\frac{3}{5}}{N}^{-\frac{1}{5}}$, from $N\le S^3$, we know $S^{\frac{3}{5}}{N}^{-\frac{1}{3}}\ge 1$. Also from $S^{\frac{1}{2}}\le N$, we know $D^2\sim S^{\frac{6}{5}}{N}^{-\frac{2}{5}}\le S$. Therefore, $I(𝒮,\mathrm{\Gamma })\lesssim S^{\frac{3}{5}}{N}^{\frac{4}{5}}+S$.

Regarding of the $r$ -rich point. Consider the $P_r(\mathrm{\Gamma })$ as $𝒮$, we have $S\le 2\left(\genfrac{}{}{0pt}{}{N}{2}\right)\le N^2$. For the case of $N\ge S^3$, we have $I(𝒮,\mathrm{\Gamma })\lesssim S^{\frac{3}{5}}{N}^{\frac{4}{5}}$ and $I(𝒮,\mathrm{\Gamma })\ge rS$. Then we have $S\lesssim N^2{r}^{-\frac{5}{2}}$ immediately.¹⁰¹⁰ 10 If $N>S^3$, the conclusion may be not established. Consider an counterexample: there is a point lying on $N$ circles and we have $P_N(\mathrm{\Gamma })\ge 1$, but let $N\to \mathrm{\infty }$ we have $P_N(\mathrm{\Gamma })\lesssim N^{-\frac{1}{2}}\to 0$.

∎

Solution 10.3.

Suppose that $\mathrm{\Gamma }$ is a set of $N$ parabolas in the plane and $𝒮$ is a set of $S$ points in the plane. Here is an example of $I(𝒮,\mathrm{\Gamma })\sim S^{\frac{2}{3}}{N}^{\frac{2}{3}}$. Take $Y=3X^2,A=1,B=X,C=X^2$, we assume $X$ as a large integer. Notice that for every integer $x$ such that $|x|\le X$, we have $(x,a{x}^2+bx+c)\in 𝒮$ since $|a{x}^2+bx+c|\le x^2+|bx|+|c|\le 3X^2\le Y$. Now we have $I(𝒮,\mathrm{\Gamma })=N\cdot 2X\sim X^4$ and $S\sim N\sim X^3$. Thus we have $I(𝒮,\mathrm{\Gamma })\sim S^{\frac{2}{3}}{N}^{\frac{2}{3}}$. ∎

Solution 10.4.

First, if there exist two irreducible algebraic curves ${\gamma }_1$ and ${\gamma }_2$ with degree at most $d$, the number of intersections of them is at most $d^2$, since Bezout Theorem. So for any set of $d^2+1$ points in ${ℝ}^2$, there is at most one curve $\gamma \in \mathrm{\Gamma }$ containing all the points.

Fix $x\in 𝒮$. Let ${\mathrm{\Gamma }}_{high}\subseteq \mathrm{\Gamma }$ be the irreducible algebraic curves containing at least $k$ points in $𝒮$ and ${\mathrm{\Gamma }}_{low}=\mathrm{\Gamma }\backslash {\mathrm{\Gamma }}_{high}$. Therefore, $I(x,\mathrm{\Gamma })=I(x,{\mathrm{\Gamma }}_{high})+I(x,{\mathrm{\Gamma }}_{low})\le \left(\genfrac{}{}{0pt}{}{S-1}{k-1}\right)+I(x,{\mathrm{\Gamma }}_{low})$. So $I(𝒮,\mathrm{\Gamma })\le S\cdot S^{k-1}+{\sum }_{x\in 𝒮}I(x,{\mathrm{\Gamma }}_{low})\le S^k+(N+2N+\mathrm{\cdots }+(k-1)N)\lesssim S^k+N$.

Let $D$ be a degree that we will choose later. By Theorem 10.3, we can find a non-zero polynomial $P$ of degree $\le D$ so that each component of the complement of $Z(P)$ contains $\lesssim S{D}^{-2}$ points of $𝒮$. Let $O_i$ be the components of ${ℝ}^2\backslash Z(P)$. For each $i$, let ${𝒮}_i=𝒮\cap O_i$ and let ${\mathrm{\Gamma }}_i\subseteq \mathrm{\Gamma }$ be the set of irreducible algebraic curves of $\mathrm{\Gamma }$ that intersect $O_i$. Let $S_i=|{𝒮}_i|$ and $N_i=|{\mathrm{\Gamma }}_i|$. Since the degree of irreducible algebraic curves is at most $d$, if it isn’t contained in $Z(P)$, then it intersects $Z(P)$ in at most $dD$ points, by Bezout Theorem. Thus every irreducible algebraic curve passes $\lesssim D$ cells, which means ${\sum }_i{N}_i\lesssim ND$.

Applying that in each cell, we get

	$I({𝒮}_{cell},\mathrm{\Gamma })$	$={\displaystyle \sum _i}I({𝒮}_i,{\mathrm{\Gamma }}_i)\lesssim {\displaystyle \sum _i}{N}_i+{\displaystyle \sum _i}{S}_i^k$
		$\lesssim ND+{(S{D}^{-2})}^{k-1}{\displaystyle \sum _i}{S}_i\le ND+S^k{D}^{-2(k-1)}$

Since every irreducible algebraic curve intersects $Z(P)$ in at most $dD$ points if it isn’t contained in $Z(P)$, we have $I({𝒮}_{alg},{\mathrm{\Gamma }}_{cell})\le NdD$. Consider the degree, the number of irreducible algebraic curves in $Z(P)$ is at most $\frac{D}{d}$.

We can prove $I(𝒮,\mathrm{\Gamma })\le S+d^2{N}^2$ by the method in Exercise 10.1. Using the inequality above, we get $I({𝒮}_{alg},{\mathrm{\Gamma }}_{alg})\le S+D^2$.

If $N\ge S^k$ or $S>N^2$, then we know $I(𝒮,\mathrm{\Gamma })\lesssim N$ or $S$ respectively. Therefore, we can now restrict to the case that $S^{\frac{1}{2}}\le N\le S^k$.

Adding them up and we know $I(𝒮,\mathrm{\Gamma })\lesssim ND+S^k{D}^{-2(k-1)}+S+D^2$. Take $D\sim S^{\frac{k}{2k-1}}{N}^{-\frac{1}{2k-1}}$, from $N\le S^k$, we know $S^{\frac{k}{2k-1}}{N}^{-\frac{1}{2k-1}}\ge 1$. Also from $S^{\frac{1}{2}}\le N$, we know $D^2\sim S^{\frac{2k}{2k-1}}{N}^{-\frac{2}{2k-1}}\le S$. Therefore, $I(𝒮,\mathrm{\Gamma })\lesssim S^{\frac{k}{2k-1}}{N}^{\frac{2k-2}{2k-1}}+S$. ∎

Solution 10.5.

We will use induction to prove the following claim firstly.

Claim. For any $\epsilon >0$, if $𝔏$ is a set of $L$ lines in the plane, and $𝒮$ is a set of $S$ points in the plane, then $I(𝒮,𝔏)\le C(\epsilon )S^{\frac{2}{3}+\epsilon }{L}^{\frac{2}{3}+\epsilon }+(D^2+1)(S+L)$.

We can observe that the conclusion is established when $S=1,L=1$. Assuming that the conclusion is true for ${𝒮}^{\prime },{𝔏}^{\prime }$ such that .

By Theorem 10.3, we can find a non-zero polynomial $P$ of degree $\le D$ so that each component of the complement of $Z(P)$ contains $\le KS{D}^{-2}$ points of $𝒮$, where $K$ is a constant. Let $k{D}^2$ is the number of cells and $O_i$ be the components of ${ℝ}^2\backslash Z(P)$. For each $i$, let ${𝒮}_i=𝒮\cap O_i$ and let ${𝔏}_i\subseteq 𝔏$ be the set of lines of $𝔏$ that intersect $O_i$. Let $S_i=|{𝒮}_i|$ and $L_i=|{𝔏}_i|$. Since every line intersects $Z(P)$ in at most $D$ points, then every line passes $D+1$ cells, which means ${\sum }_{i=1}^{k{D}^2}{L}_i\le L(D+1)$.

If $N\ge S^2$ or $S>N^2$, then we know $I(𝒮,𝔏)\le 2N$ or $2S$ respectively. Therefore, we can now restrict to the case that $S^{\frac{1}{2}}\le N\le S^2$.

In following content, we assume that

which are possible when $D=D(\epsilon )$ and $C(\epsilon )$ are both large, where .

Applying that in each cell, using Jensen’s inequality, we get

	$I({𝒮}_{cell},𝔏)$	$={\displaystyle \sum _{i=1}^{k{D}^2}}I({𝒮}_i,{𝔏}_i)\le {\displaystyle \sum _{i=1}^{k{D}^2}}C(\epsilon )\left({(K{S}_i{D}^{-2})}^p{L}_i^p\right)+(D^2+1)(S_i+L_i)$
		$\le C(\epsilon )K^p{D}^{-2p}(k{D}^2)S^p{\left({\displaystyle \frac{L(D+1)}{k{D}^2}}\right)}^p+(D^2+1)(S+L(D+1))$
		$=C(\epsilon )K^p{D}^{2-4p}{(D+1)}^p{k}^{1-p}{S}^p{L}^p+(D^2+1)(2+D)S^p{L}^p$
		$\le C(\epsilon )S^p{L}^p$

Also, similar to the proof of Theorem 10.10, we know $I({𝒮}_{alg},{𝔏}_{cell})\le LD$ and $I({𝒮}_{alg},{𝔏}_{alg})\le S+D^2$. Then we know

$$I({𝒮}_{alg},{𝔏}_{cell})+I({𝒮}_{alg},{𝔏}_{alg})\le LD+S+D^2\le (D^2+1)(S+L)$$

since $S,L\ge 1$ and $D\ge 1$. Now adding them up and we finish the proof of this claim.

Notice that $C(\epsilon )>D^2+1$, we have

$$I(𝒮,𝔏)\le C(\epsilon )S^{\frac{2}{3}+\epsilon }{L}^{\frac{2}{3}+\epsilon }+(D^2+1)(S+L)\le C(\epsilon )\left(S^{\frac{2}{3}+\epsilon }{L}^{\frac{2}{3}+\epsilon }+S+L\right)$$

∎

Solution 10.6.

Fix $x\in 𝒮$. Let $N_x$ be the number of planes of $\mathrm{\Gamma }$ that contain $x$ and no other point of $𝒮$. For each other point $y\in S$, there is at most two planes of $\mathrm{\Gamma }$ containing $x$ and $y$. Therefore, $I(x,\mathrm{\Gamma })\le 2S+N_x$. So $I(𝒮,\mathrm{\Gamma })\le 2S^2+{\sum }_{x\in 𝒮}{N}_x\le 2S^2+N$.

Fix $\gamma \in \mathrm{\Gamma }$. Let ${𝒮}_{high}\subseteq 𝒮$ be the points contained in least 3 planes in $\mathrm{\Gamma }$ and ${𝒮}_{low}=𝒮\backslash {𝒮}_{high}$. Therefore, $I(𝒮,\gamma )=I({𝒮}_{high},\gamma )+I({𝒮}_{low},\gamma )\le \left(\genfrac{}{}{0pt}{}{N-1}{2}\right)+I({𝒮}_{low},\gamma )$. So $I(𝒮,\mathrm{\Gamma })\le N\cdot \frac{N^2}{2}+{\sum }_{\gamma \in \mathrm{\Gamma }}I({𝒮}_{low},\gamma )\le \frac{N^3}{2}+(S+2S)\le \frac{N^3}{2}+3S$.

Claim. For any $\epsilon >0$, if $\mathrm{\Gamma }$ is a set of $N$ planes in ${ℝ}^3$, and $𝒮$ is a set of $S$ points in ${ℝ}^3$, then $I(𝒮,\mathrm{\Gamma })\le C(\epsilon )S^{\frac{4}{5}+\epsilon }{N}^{\frac{3}{5}+\epsilon }+\left(D^3+3\right)(S+N)$.

We can observe that the conclusion is established when $S=1,L=1$. Assuming that the conclusion is true for ${𝒮}^{\prime },{𝔏}^{\prime }$ such that .

By Theorem 10.3, we can find a non-zero polynomial $P$ of degree $\le D$ so that each component of the complement of $Z(P)$ contains $\le KS{D}^{-3}$ points of $𝒮$, where $K$ is a constant. Let $k{D}^3$ is the number of cells and $O_i$ be the components of ${ℝ}^3\backslash Z(P)$. For each $i$, let ${𝒮}_i=𝒮\cap O_i$ and let ${\mathrm{\Gamma }}_i\subseteq \mathrm{\Gamma }$ be the set of planes of $\mathrm{\Gamma }$ that intersect $O_i$. Let $S_i=|{𝒮}_i|$ and $N_i=|{\mathrm{\Gamma }}_i|$. According to Harnack inequality, every plane intersects $Z(P)$ in at most $M{D}^2$ cells, which means ${\sum }_{i=1}^{k{D}^3}{N}_i\le MN{D}^2$, where $M$ is a constant. Assume ${\mathrm{\Gamma }}_{alg}$ is the set of planes of $\mathrm{\Gamma }$ that lie in $Z(P)$ and ${\mathrm{\Gamma }}_{cell}=\mathrm{\Gamma }\backslash {\mathrm{\Gamma }}_{alg}$.

¹¹¹¹ 11 Idea of this part comes from [2].

Let ${𝒮}_{alg}$ be the set of points of $𝒮$ that lie in $Z(P)$ and ${𝒮}_{alg}^{alg}$ the set of points of ${𝒮}_{alg}$ that lie in $Z(Q)$. Again by Theorem 10.3, we can find a non-zero polynomial $Q$ of degree $\le D$ which is co-prime to $P$ so that each component of the complement of $Z(Q)$ contains $\le TS{D}^{-3}$ points of ${𝒮}_{alg}$, where $T$ is a constant. (That is possible because if not, we can consider a small perturbation of $Q$ to make they are co-prime.) Let $t{D}^3$ is the number of cells and $U_i$ be the components of ${ℝ}^3\backslash Z(Q)$. For each $i$, let ${𝒮}_{alg}^i={𝒮}_{alg}\cap U_i$ and let ${\mathrm{\Gamma }}^i\subseteq \mathrm{\Gamma }$ be the set of planes of $\mathrm{\Gamma }$ that intersect $U_i$. Let $s_i=|{𝒮}_{alg}^i|$ and $n_i=|{\mathrm{\Gamma }}^i|$. According to Harnack inequality, every plane intersects $Z(Q)$ in at most $m{D}^2$ cells, which means ${\sum }_{i=1}^{t{D}^3}{n}_i\le mN{D}^2$, where $m$ is a constant.

If $N>S^2$ or $S>N^3$, then we know $I(𝒮,𝔏)\le 3N$ or $4S$ respectively. Therefore, we can now restrict to the case that $S^{\frac{1}{3}}\le N\le S^2$.

In following content, we assume that

and

$$C(\epsilon )\ge \frac{(D^3+3)(M{D}^2+m{D}^2+2)}{1-K^p{k}^{1-p}{D}^{3-3p-q}{M}^q-T^p{t}^{1-p}{D}^{3-3p-q}{m}^q}$$

which are possible when $D=D(\epsilon )$ and $C(\epsilon )$ are both large, where $p=\frac{3}{5}+\epsilon$ and .

Applying that in each cell, using Jensen’s inequality, let ${𝒮}_{cell}=𝒮\backslash {𝒮}_{alg}$, we get

	$I({𝒮}_{cell},\mathrm{\Gamma })$	$={\displaystyle \sum _{i=1}^{k{D}^3}}I({𝒮}_i,{\mathrm{\Gamma }}_i)\le {\displaystyle \sum _{i=1}^{k{D}^3}}C(\epsilon )\left({(K{S}_i{D}^{-3})}^p{N}_i^q\right)+\left(D^3+3\right)(S_i+N_i)$
		$\le C(\epsilon )K^p{D}^{-3p}(k{D}^3)S^p{\left({\displaystyle \frac{MN{D}^2}{k{D}^3}}\right)}^q+\left(D^3+3\right)(S+M{D}^{2}N)$
		$=C(\epsilon )K^p{k}^{1-p}{D}^{3-3p-q}{M}^q{S}^p{N}^q+\left(D^3+3\right)(1+M{D}^2)S^p{N}^q$

Assume ${𝒮}_{alg}^{cell}={𝒮}_{alg}\backslash {𝒮}_{alg}^{alg}$, we have

	$I({𝒮}_{alg}^{cell},\mathrm{\Gamma })$	$={\displaystyle \sum _{i=1}^{t{D}^3}}I({𝒮}_{alg}^i,{\mathrm{\Gamma }}^i)\le {\displaystyle \sum _{i=1}^{t{D}^3}}C(\epsilon )\left({(T{s}_i{D}^{-3})}^p{n}_i^q\right)+\left(D^3+3\right)(s_i+n_i)$
		$\le C(\epsilon )T^p{D}^{-3p}(t{D}^3)S^p{\left({\displaystyle \frac{mN{D}^2}{t{D}^3}}\right)}^q+\left(D^3+3\right)(S+m{D}^{2}N)$
		$=C(\epsilon )T^p{t}^{1-p}{D}^{3-3p-q}{m}^q{S}^p{N}^q+\left(D^3+3\right)(1+m{D}^2)S^p{N}^q$

Now we know $I({𝒮}_{cell},\mathrm{\Gamma })+I({𝒮}_{alg}^{cell},\mathrm{\Gamma })\le C(\epsilon )S^p{N}^q$.

Consider Bezout Theorem, each plane of $\mathrm{\Gamma }$ has at most $D^2$ intersection points with $Z(P)\cap Z(Q)$, and so it has at most $D^2$ incidences with ${𝒮}_{alg}$, we know $I({𝒮}_{alg}^{alg},{\mathrm{\Gamma }}_{cell})\le N{D}^2$. And using the inequality above, we have $I({𝒮}_{alg}^{alg},{\mathrm{\Gamma }}_{alg})\le 3S+\frac{D^3}{2}$. Then we know

$$I({𝒮}_{alg}^{alg},{\mathrm{\Gamma }}_{cell})+I({𝒮}_{alg}^{alg},{\mathrm{\Gamma }}_{alg})\le N{D}^2+3S+\frac{D^3}{2}\le (D^3+3)(S+N)$$

since $S,L\ge 1$ and $D\ge 1$. Now adding them up and we finish the proof of this claim.

Notice that $C(\epsilon )>D^3+3$, we have

$$I(𝒮,\mathrm{\Gamma })\le C(\epsilon )S^{\frac{4}{5}+\epsilon }{N}^{\frac{3}{5}+\epsilon }+(D^3+3)(S+N)\le C(\epsilon )\left(S^{\frac{4}{5}+\epsilon }{N}^{\frac{3}{5}+\epsilon }+S+N\right)$$

∎

Solution 10.7.

Considering a circle $S$ large enough, which isn’t contained in $Z(P)$, we know $|Z(P)\cap S|\le 2D$ by Bezout Theorem. Notice that every unbounded component must intersect $S$, we know the number of unbounded components is at most $2D$.

Regarding the bounded components, in every bounded component $U$, we know $P$ must reach a local maximum or a local minimum, which means there is a critical point in $U$. If there’s no common factor of ${\partial }_{1}P$ and ${\partial }_{2}P$, then the number of points such that ${\partial }_{1}P={\partial }_{2}P=0$ is at most $(\mathrm{deg}{\partial }_{1}P)(\mathrm{deg}{\partial }_{2}P)\le {(D-1)}^2$. Then the number of bounded components is at most ${(D-1)}^2$.

For the case of ${\partial }_{1}P$ and ${\partial }_{2}P$ have at least one common factor, we can consider the polynomial $Q=P+w_1{x}_1+w_2{x}_2$. Let $m=\min U\text{ bounded}{\max }_{x\in U}|P(x)|$, we take $w_1$ and $w_2$ small enough such that for $x$ in every bounded component. So for every bounded $U$, there exist a point $x$ in it such that $|Q(x)|\ge m-|w_1{x}_1+w_2{x}_2|>\frac{m}{2}$. And for $x\in \partial U\subseteq Z(P)$, we know . Thus there is a critical point of $Q$ in $U$. Notice that, for $c$ small enough (for all where $K$ is a constant depending $P$), ${\partial }_{1}P+c$ and ${\partial }_{2}P+c$ have no common factor, we know that we can always make ${\partial }_{1}Q$ and ${\partial }_{2}Q$ have no common factor. Therefore we know the number of bounded components is at most ${(D-1)}^2$. The number of components of ${ℝ}^2\backslash Z(P)$ is at most $D^2+1\sim D^2$. ∎

Solution 10.8.

Suppose that there are three unit 2-spheres $S_1,S_2,S_3$. Notice that $S_1\cap S_2$ and $S_1\cap S_3$ are both circles and $S_1\cap S_2\cap S_3=(S_1\cap S_2)\cap (S_1\cap S_3)$, we know $|S_1\cap S_2\cap S_3|\le 2$ since two circles intersect in at most 2 points.

Fix $x\in 𝒮$. Let ${\mathrm{\Gamma }}_{high}\subseteq \mathrm{\Gamma }$ be the unit 2-spheres containing at least $3$ points in $𝒮$ and ${\mathrm{\Gamma }}_{low}=\mathrm{\Gamma }\backslash {\mathrm{\Gamma }}_{high}$. Notice that 3 points can determine at most two unit 2-spheres. Therefore, $I(x,\mathrm{\Gamma })=I(x,{\mathrm{\Gamma }}_{high})+I(x,{\mathrm{\Gamma }}_{low})\le 2\left(\genfrac{}{}{0pt}{}{S-1}{2}\right)+I(x,{\mathrm{\Gamma }}_{low})$. So $I(𝒮,\mathrm{\Gamma })\le S\cdot S^2+{\sum }_{x\in 𝒮}I(x,{\mathrm{\Gamma }}_{low})\le S^3+(N+2N)=S^3+3N$.

Fix $\gamma \in \mathrm{\Gamma }$. Let ${𝒮}_{high}\subseteq 𝒮$ be the points contained in least 3 unit 2-spheres in $\mathrm{\Gamma }$ and ${𝒮}_{low}=𝒮\backslash {𝒮}_{high}$. Notice that 3 unit 2-spheres intersect in at most two points. Therefore, $I(𝒮,\gamma )=I({𝒮}_{high},\gamma )+I({𝒮}_{low},\gamma )\le 2\left(\genfrac{}{}{0pt}{}{N-1}{2}\right)+I({𝒮}_{low},\gamma )$. So $I(𝒮,\mathrm{\Gamma })\le N\cdot N^2+{\sum }_{\gamma \in \mathrm{\Gamma }}I({𝒮}_{low},\gamma )\le N^3+(S+2S)=N^3+3S$.

Claim. For any $\epsilon >0$, if $\mathrm{\Gamma }$ is a set of $N$ unit 2-spheres in ${ℝ}^3$, and $𝒮$ is a set of $S$ points in ${ℝ}^3$, then $I(𝒮,\mathrm{\Gamma })\le C(\epsilon )S^{\frac{3}{4}+\epsilon }{N}^{\frac{3}{4}+\epsilon }+\left(2D^3+3\right)(S+N)$.

By Theorem 10.3, we can find a non-zero polynomial $P$ of degree $\le D$ so that each component of the complement of $Z(P)$ contains $\le KS{D}^{-3}$ points of $𝒮$, where $K$ is a constant. Let $k{D}^3$ is the number of cells and $O_i$ be the components of ${ℝ}^3\backslash Z(P)$. For each $i$, let ${𝒮}_i=𝒮\cap O_i$ and let ${\mathrm{\Gamma }}_i\subseteq \mathrm{\Gamma }$ be the set of unit 2-spheres of $\mathrm{\Gamma }$ that intersect $O_i$. Let $S_i=|{𝒮}_i|$ and $N_i=|{\mathrm{\Gamma }}_i|$. According to spherical version of the Harnack inequality, every unit 2-sphere intersects $Z(P)$ in at most $M{D}^2$ cells, which means ${\sum }_{i=1}^{k{D}^3}{N}_i\le MN{D}^2$, where $M$ is a constant. Assume ${\mathrm{\Gamma }}_{alg}$ is the set of unit 2-spheres of $\mathrm{\Gamma }$ that lie in $Z(P)$ and ${\mathrm{\Gamma }}_{cell}=\mathrm{\Gamma }\backslash {\mathrm{\Gamma }}_{alg}$.

Let ${𝒮}_{alg}$ be the set of points of $𝒮$ that lie in $Z(P)$ and ${𝒮}_{alg}^{alg}$ the set of points of ${𝒮}_{alg}$ that lie in $Z(Q)$. Again by Theorem 10.3, we can find a non-zero polynomial $Q$ of degree $\le D$ which is co-prime to $P$ so that each component of the complement of $Z(Q)$ contains $\le TS{D}^{-3}$ points of ${𝒮}_{alg}$, where $T$ is a constant. (That is possible because if not, we can consider a small perturbation of $Q$ to make they are co-prime.) Let $t{D}^3$ is the number of cells and $U_i$ be the components of ${ℝ}^3\backslash Z(Q)$. For each $i$, let ${𝒮}_{alg}^i={𝒮}_{alg}\cap U_i$ and let ${\mathrm{\Gamma }}^i\subseteq \mathrm{\Gamma }$ be the set of unit 2-spheres of $\mathrm{\Gamma }$ that intersect $U_i$. Let $s_i=|{𝒮}_{alg}^i|$ and $n_i=|{\mathrm{\Gamma }}^i|$. According to spherical version of the Harnack inequality, every unit 2-spheres intersects $Z(Q)$ in at most $m{D}^2$ cells, which means ${\sum }_{i=1}^{t{D}^3}{n}_i\le mN{D}^2$, where $m$ is a constant.

If $N>S^3$ or $S>N^3$, then we know $I(𝒮,𝔏)\le 4N$ or $4S$ respectively. Therefore, we can now restrict to the case that $S^{\frac{1}{3}}\le N\le S^3$.

In following content, we assume that

and

$$C(\epsilon )\ge \frac{(D^3+3)(M{D}^2+m{D}^2+2)}{1-K^p{k}^{1-p}{D}^{3-3p-q}{M}^q-T^p{t}^{1-p}{D}^{3-3p-q}{m}^q}$$

which are possible when $D=D(\epsilon )$ and $C(\epsilon )$ are both large, where .

Applying that in each cell, using Jensen’s inequality, let ${𝒮}_{cell}=𝒮\backslash {𝒮}_{alg}$, we get

	$I({𝒮}_{cell},\mathrm{\Gamma })$	$={\displaystyle \sum _{i=1}^{k{D}^3}}I({𝒮}_i,{\mathrm{\Gamma }}_i)\le {\displaystyle \sum _{i=1}^{k{D}^3}}C(\epsilon )\left({(K{S}_i{D}^{-3})}^p{N}_i^p\right)+\left(2D^3+3\right)(S_i+N_i)$
		$\le C(\epsilon )K^p{D}^{-3p}(k{D}^3)S^p{\left({\displaystyle \frac{MN{D}^2}{k{D}^3}}\right)}^p+\left(2D^3+3\right)(S+M{D}^{2}N)$
		$=C(\epsilon )K^p{k}^{1-p}{D}^{3-4p}{M}^p{S}^p{N}^p+\left(2D^3+3\right)(1+M{D}^2)S^p{N}^p$

Assume ${𝒮}_{alg}^{cell}={𝒮}_{alg}\backslash {𝒮}_{alg}^{alg}$, we have

	$I({𝒮}_{alg}^{cell},\mathrm{\Gamma })$	$={\displaystyle \sum _{i=1}^{t{D}^3}}I({𝒮}_{alg}^i,{\mathrm{\Gamma }}^i)\le {\displaystyle \sum _{i=1}^{t{D}^3}}C(\epsilon )\left({(T{s}_i{D}^{-3})}^p{n}_i^p\right)+\left(2D^3+3\right)(s_i+n_i)$
		$\le C(\epsilon )T^p{D}^{-3p}(t{D}^3)S^p{\left({\displaystyle \frac{mN{D}^2}{t{D}^3}}\right)}^p+\left(2D^3+3\right)(S+m{D}^{2}N)$
		$=C(\epsilon )T^p{t}^{1-p}{D}^{3-4p}{m}^p{S}^p{N}^p+\left(2D^3+3\right)(1+m{D}^2)S^p{N}^p$
		$\le C(\epsilon )S^p{N}^p$

Now we know $I({𝒮}_{cell},\mathrm{\Gamma })+I({𝒮}_{alg}^{cell},\mathrm{\Gamma })\le C(\epsilon )S^p{N}^q$.

Consider Bezout Theorem and that sphere is irreducible in $ℝ$, each unit 2-sphere of $\mathrm{\Gamma }$ has at most $2D^2$ intersection points with $Z(P)\cap Z(Q)$, and so it has at most $2D^2$ incidences with ${𝒮}_{alg}$, we know $I({𝒮}_{alg}^{alg},{\mathrm{\Gamma }}_{cell})\le 2N{D}^2$. Consider the degree, the number of unit 2-sphere in $Z(P)$ is at most $\frac{D}{2}$. And using the inequality above, we have $I({𝒮}_{alg}^{alg},{\mathrm{\Gamma }}_{alg})\le 3S+{\left(\frac{D}{2}\right)}^3$. Then we know

$$I({𝒮}_{alg}^{alg},{\mathrm{\Gamma }}_{cell})+I({𝒮}_{alg}^{alg},{\mathrm{\Gamma }}_{alg})\le 2N{D}^2+3S+{\left(\frac{D}{2}\right)}^3\le (2D^3+3)(S+N)$$

since $S,L\ge 1$ and $D\ge 1$. Now adding them up and we finish the proof of this claim.

Notice that $C(\epsilon )>2D^3+3$, we have

$$I(𝒮,\mathrm{\Gamma })\le C(\epsilon )S^{\frac{3}{4}+\epsilon }{N}^{\frac{3}{4}+\epsilon }+(D^3+3)(S+N)\le C(\epsilon )\left(S^{\frac{3}{4}+\epsilon }{N}^{\frac{3}{4}+\epsilon }+S+N\right)$$

Take $\mathrm{\Gamma }$ as the unit 2-spheres centered at points in $𝒮$ and we have $N=S$. And we can get that $N$ points in ${ℝ}^3$ determine at most $N^{\frac{3}{2}+\epsilon }$ unit distances immediately. ∎

Solution 10.9.

Fix $x\in 𝒮$. Let ${\mathrm{\Gamma }}_{high}\subseteq \mathrm{\Gamma }$ be the 2-spheres containing at least $11$ points in $𝒮$ and ${\mathrm{\Gamma }}_{low}=\mathrm{\Gamma }\backslash {\mathrm{\Gamma }}_{high}$. Notice that 11 points can determine a sphere. Therefore, $I(x,\mathrm{\Gamma })=I(x,{\mathrm{\Gamma }}_{high})+I(x,{\mathrm{\Gamma }}_{low})\le \left(\genfrac{}{}{0pt}{}{S-1}{10}\right)+I(x,{\mathrm{\Gamma }}_{low})$. So $I(𝒮,\mathrm{\Gamma })\le S\cdot S^2+{\sum }_{x\in 𝒮}I(x,{\mathrm{\Gamma }}_{low})\le S^{1}1+(N+2N+\mathrm{\cdots }+10N)=S^{11}+55N$.

Fix $\gamma \in \mathrm{\Gamma }$. Let $S_{\gamma }$ be the number of points of $𝒮$ that contained in $\gamma$ and no other sphere of $\mathrm{\Gamma }$. Notice that two spheres intersect in at most 10 points. Therefore, $I(𝒮,\gamma )\le S_{\gamma }+10N$, so we have $I(𝒮,\mathrm{\Gamma })\le N\cdot (10N)+{\sum }_{\gamma \in \mathrm{\Gamma }}{S}_{\gamma }\le 10N^2+S\le 10N^3+S$. ¹²¹² 12 Since here we can use a more accurate estimate of $10N^2+S$, it is possible that the result of this problem can be better.

Claim. For any $\epsilon >0$, if $\mathrm{\Gamma }$ is a set of $N$ 2-spheres in ${ℝ}^3$, and $𝒮$ is a set of $S$ points in ${ℝ}^3$, then $I(𝒮,\mathrm{\Gamma })\le C(\epsilon )S^{\frac{11}{16}+\epsilon }{N}^{\frac{15}{16}+\epsilon }+\left(2D^3+1\right)(S+N)$.

By Theorem 10.3, we can find a non-zero polynomial $P$ of degree $\le D$ so that each component of the complement of $Z(P)$ contains $\le KS{D}^{-3}$ points of $𝒮$, where $K$ is a constant. Let $k{D}^3$ is the number of cells and $O_i$ be the components of ${ℝ}^3\backslash Z(P)$. For each $i$, let ${𝒮}_i=𝒮\cap O_i$ and let ${\mathrm{\Gamma }}_i\subseteq \mathrm{\Gamma }$ be the set of 2-spheres of $\mathrm{\Gamma }$ that intersect $O_i$. Let $S_i=|{𝒮}_i|$ and $N_i=|{\mathrm{\Gamma }}_i|$. According to spherical version of the Harnack inequality, every 2-sphere intersects $Z(P)$ in at most $M{D}^2$ cells, which means ${\sum }_{i=1}^{k{D}^3}{N}_i\le MN{D}^2$, where $M$ is a constant. Assume ${\mathrm{\Gamma }}_{alg}$ is the set of 2-spheres of $\mathrm{\Gamma }$ that lie in $Z(P)$ and ${\mathrm{\Gamma }}_{cell}=\mathrm{\Gamma }\backslash {\mathrm{\Gamma }}_{alg}$.

Let ${𝒮}_{alg}$ be the set of points of $𝒮$ that lie in $Z(P)$ and ${𝒮}_{alg}^{alg}$ the set of points of ${𝒮}_{alg}$ that lie in $Z(Q)$. Again by Theorem 10.3, we can find a non-zero polynomial $Q$ of degree $\le D$ which is co-prime to $P$ so that each component of the complement of $Z(Q)$ contains $\le TS{D}^{-3}$ points of ${𝒮}_{alg}$, where $T$ is a constant. (That is possible because if not, we can consider a small perturbation of $Q$ to make they are co-prime.) Let $t{D}^3$ is the number of cells and $U_i$ be the components of ${ℝ}^3\backslash Z(Q)$. For each $i$, let ${𝒮}_{alg}^i={𝒮}_{alg}\cap U_i$ and let ${\mathrm{\Gamma }}^i\subseteq \mathrm{\Gamma }$ be the set of 2-spheres of $\mathrm{\Gamma }$ that intersect $U_i$. Let $s_i=|{𝒮}_{alg}^i|$ and $n_i=|{\mathrm{\Gamma }}^i|$. According to spherical version of the Harnack inequality, every 2-spheres intersects $Z(Q)$ in at most $m{D}^2$ cells, which means ${\sum }_{i=1}^{t{D}^3}{n}_i\le mN{D}^2$, where $m$ is a constant.

If $N>S^{11}$ or $S>N^3$, then we know $I(𝒮,𝔏)\le 56N$ or $11S$ respectively. Therefore, we can now restrict to the case that $S^{\frac{1}{3}}\le N\le S^{11}$.

In following content, we assume that

and

$$C(\epsilon )\ge \frac{(2D^3+1)(M{D}^2+m{D}^2+2)}{1-K^p{k}^{1-p}{D}^{3-3p-q}{M}^q-T^p{t}^{1-p}{D}^{3-3p-q}{m}^q}$$

which are possible when $D=D(\epsilon )$ and $C(\epsilon )$ are both large, where $p=\frac{11}{16}+\epsilon$ and .

Applying that in each cell, using Jensen’s inequality, let ${𝒮}_{cell}=𝒮\backslash {𝒮}_{alg}$, we get

	$I({𝒮}_{cell},\mathrm{\Gamma })$	$={\displaystyle \sum _{i=1}^{k{D}^3}}I({𝒮}_i,{\mathrm{\Gamma }}_i)\le {\displaystyle \sum _{i=1}^{k{D}^3}}C(\epsilon )\left({(K{S}_i{D}^{-3})}^p{N}_i^q\right)+\left(2D^3+1\right)(S_i+N_i)$
		$\le C(\epsilon )K^p{D}^{-3p}(k{D}^3)S^p{\left({\displaystyle \frac{MN{D}^2}{k{D}^3}}\right)}^q+\left(2D^3+1\right)(S+M{D}^{2}N)$
		$=C(\epsilon )K^p{k}^{1-p}{D}^{3-3p-q}{M}^q{S}^p{N}^q+\left(2D^3+1\right)(1+M{D}^2)S^p{N}^q$

Assume ${𝒮}_{alg}^{cell}={𝒮}_{alg}\backslash {𝒮}_{alg}^{alg}$, we have

	$I({𝒮}_{alg}^{cell},\mathrm{\Gamma })$	$={\displaystyle \sum _{i=1}^{t{D}^3}}I({𝒮}_{alg}^i,{\mathrm{\Gamma }}^i)\le {\displaystyle \sum _{i=1}^{t{D}^3}}C(\epsilon )\left({(T{s}_i{D}^{-3})}^p{n}_i^q\right)+\left(2D^3+1\right)(s_i+n_i)$
		$\le C(\epsilon )T^p{D}^{-3p}(t{D}^3)S^p{\left({\displaystyle \frac{mN{D}^2}{t{D}^3}}\right)}^q+\left(2D^3+1\right)(S+m{D}^{2}N)$
		$=C(\epsilon )T^p{t}^{1-p}{D}^{3-3p-q}{m}^q{S}^p{N}^q+\left(2D^3+1\right)(1+m{D}^2)S^p{N}^q$

Now we know $I({𝒮}_{cell},\mathrm{\Gamma })+I({𝒮}_{alg}^{cell},\mathrm{\Gamma })\le C(\epsilon )S^p{N}^q$.

Consider Bezout Theorem and that sphere is irreducible in $ℝ$, each 2-sphere of $\mathrm{\Gamma }$ has at most $2D^2$ intersection points with $Z(P)\cap Z(Q)$, and so it has at most $2D^2$ incidences with ${𝒮}_{alg}$, we know $I({𝒮}_{alg}^{alg},{\mathrm{\Gamma }}_{cell})\le 2N{D}^2$. Consider the degree, the number of unit 2-sphere in $Z(P)$ is at most $\frac{D}{2}$. And using the inequality above, we have $I({𝒮}_{alg}^{alg},{\mathrm{\Gamma }}_{alg})\le S+10{\left(\frac{D}{2}\right)}^3\le S+2D^3$. Then we know

$$I({𝒮}_{alg}^{alg},{\mathrm{\Gamma }}_{cell})+I({𝒮}_{alg}^{alg},{\mathrm{\Gamma }}_{alg})\le 2N{D}^2+S+2D^3\le (2D^3+1)(S+N)$$

since $S,L\ge 1$ and $D\ge 1$. Now adding them up and we finish the proof of this claim.

Notice that $C(\epsilon )>2D^3+1$, we have

$$I(𝒮,\mathrm{\Gamma })\le C(\epsilon )S^{\frac{11}{16}+\epsilon }{N}^{\frac{15}{16}+\epsilon }+(2D^3+1)(S+N)\le C(\epsilon )\left(S^{\frac{11}{16}+\epsilon }{N}^{\frac{15}{16}+\epsilon }+S+N\right)$$

∎

Solution 10.10.

By Theorem 10.3, there exist a polynomial $P\in {\mathrm{Poly}}_D({ℝ}^3)$ such that ${ℝ}^3\backslash Z(P)$ is decomposed into $\sim D^3$ cells, satisfying $|O_i\cap P_r(𝔏)|\lesssim D^{-3}|P_r(𝔏)|$ for every $i$. We have $|P_r(𝔏)|=|P_r(𝔏)\cap Z(P)|+|P_r(𝔏)\cap ({ℝ}^3)\backslash Z(P)|$.

For the case of $|P_r(𝔏)\cap Z(P)|\le |P_r(𝔏)\cap ({ℝ}^3)\backslash Z(P)|$, we know for every $O_i$, we have $|P_r(𝔏)|\lesssim D^3|P_r(𝔏)\cap O_i|\le D^3|P_r({𝔏}_i)|$, where ${𝔏}_i\subseteq 𝔏$ is set of lines that intersect $O_i$. Notice that every line intersects at most $D+1$ cells, we have ${\sum }_i|{𝔏}_i|\le (D+1)L\lesssim DL$. Since the number of cells is $\sim D^3$, there exist a cell $O_i$ such that $|{𝔏}_i|\lesssim L{D}^{-2}$. So there is

$$|P_r(𝔏)|\lesssim D^3|P_r({𝔏}_i)|\le D^{3}I(B,D,|{𝔏}_i|,r)\le D^{3}I(B,D,KL{D}^{-2},r)$$

For the case of $|P_r(𝔏)\cap Z(P)|\ge |P_r(𝔏)\cap ({ℝ}^3)\backslash Z(P)|$, we know $|P_r(𝔏)|\le 2|P_r(𝔏)\cap Z(P)|\lesssim DL{r}^{-1}+B^2{r}^{-3}$ by Lemma 10.15.

Therefore, we know $I(B,D,L,r)\lesssim \left(D^{3}I(B,D,KL{D}^{-2},r)+DL{r}^{-1}+B^2{r}^{-3}\right)$, which means $I(B,D,L,r)\le M\left(D^{3}I(B,D,KL{D}^{-2},r)+DL{r}^{-1}+B^2{r}^{-3}\right)$. Take $C=\max \{M,K\}$, we get

$$I(B,D,L,r)\lesssim C\left(D^{3}I(B,D,CL{D}^{-2},r)+DL{r}^{-1}+B^2{r}^{-3}\right)$$

∎

Solution 10.11.

We will use induction on $L$ to prove this conclusion. It obvious that it is established for $L=1$. We know there is a constant $K$ such that $I(B,D,L,r)\le K\left(D^{3}I(B,D,KL{D}^{-2},r)+DL{r}^{-1}+B^2{r}^{-3}\right)$. We assume that this conclusion is established for ${𝔏}^{\prime }$ with $|{𝔏}^{\prime }|=L^{\prime }\le L$, that is, $I(B,D,L^{\prime },r)\le C(\epsilon )B^{\frac{1}{2}-\epsilon }{(L^{\prime })}^{\frac{3}{2}+\epsilon }{r}^{-2}$.

Suppose that $C(\epsilon )$ and $D=D(\epsilon )$ large enough, satisfying the following four conditions:

$$K^{\frac{5}{2}+\epsilon }{D}^{-2\epsilon }\le \frac{1}{3},K{D}^{-2}\le \frac{1}{2},KD\le \frac{1}{6}C(\epsilon ),K{B}^{\frac{3}{2}+\epsilon }\le \frac{1}{3}C(\epsilon )$$

Since $KL{D}^{-2}\le \frac{L}{2}$, we can use the induction hypothesis that

$$I(B,D,KL{D}^{-2},r)\le C(\epsilon )B^{\frac{1}{2}-\epsilon }{(KL{D}^{-2})}^{\frac{3}{2}+\epsilon }{r}^{-2}$$

So we have

$$I(B,D,L,r)\le K\left(D^3\cdot C(\epsilon )B^{\frac{1}{2}-\epsilon }{(KL{D}^{-2})}^{\frac{3}{2}+\epsilon }{r}^{-2}+DL{r}^{-1}+B^2{r}^{-3}\right)$$

that is

$$I(B,D,L,r)\le C(\epsilon )K^{\frac{5}{2}+\epsilon }{D}^{-2\epsilon }{B}^{\frac{1}{2}-\epsilon }{L}^{\frac{3}{2}+\epsilon }{r}^{-2}+KDL{r}^{-1}+K{B}^2{r}^{-3}$$

Use the conditions above, we have

$$C(\epsilon )K^{\frac{5}{2}+\epsilon }{D}^{-2\epsilon }{B}^{\frac{1}{2}-\epsilon }{L}^{\frac{3}{2}+\epsilon }{r}^{-2}\le \frac{1}{3}C(\epsilon )B^{(1/2)-\epsilon }{L}^{(3/2)+\epsilon }{r}^{-2}$$

$$KDL{r}^{-1}\le \frac{1}{3}C(\epsilon )B^{(1/2)-\epsilon }{L}^{(3/2)+\epsilon }{r}^{-2}$$

$$K{B}^2{r}^{-3}\le \frac{1}{3}C(\epsilon )B^{(1/2)-\epsilon }{L}^{(3/2)+\epsilon }{r}^{-2}$$

Thus we have $I(B,D,L,r)\le C(\epsilon )B^{\frac{1}{2}-\epsilon }{L}^{\frac{3}{2}+\epsilon }{r}^{-2}$, which leads the conclusion. ∎

Solution 10.12.

For the case of $r>2L^{\frac{1}{2}}$, then $P_r(𝔏)\le 2L{r}^{-1}$ by Lemma 10.16.

If $r\le 2L^{\frac{1}{2}}$, notice that Lemma 10.15 is also available for ${ℝ}^n$ and also sharp, because all $B$ lines can be on the same 2-plane contained by $Z(P)$. Similar to Exercise 10.10, we can prove that there exists a constant $K$ such that

$$I(B,D,L,r)\le K\left(D^{n}I(B,D,CL{D}^{-(n-1)},r)+DL{r}^{-1}+B^2{r}^{-3}\right)$$

Claim. We have $I(B,D,L,r)\le C(\epsilon )B^{\frac{n-2}{n-1}-\epsilon }{L}^{\frac{n}{n-1}+\epsilon }{r}^{-\frac{n+1}{n-1}}$.

We use induction on $L$ to prove this conclusion. It obvious that it is established for $L=1$. We assume that this conclusion is established for ${𝔏}^{\prime }$ with $|{𝔏}^{\prime }|=L^{\prime }\le L$, that is, $I(B,D,L^{\prime },r)\le C(\epsilon )B^{\frac{n-2}{n-1}-\epsilon }{(L^{\prime })}^{\frac{n}{n-1}+\epsilon }{r}^{-\frac{n+1}{n-1}}$.

Suppose that $C(\epsilon )$ and $D=D(\epsilon )$ large enough, satisfying the following four conditions:

$$K^{\frac{2n-1}{n-1}+\epsilon }{D}^{-(n-1)\epsilon }\le \frac{1}{3},K{D}^{-(n-1)}\le \frac{1}{2},KD\le \frac{1}{3\cdot 2^{\frac{2}{n-1}}}C(\epsilon ),K{B}^{\frac{n}{n-1}+\epsilon }\le \frac{1}{3}C(\epsilon )$$

Since $KL{D}^{-(n-1)}\le \frac{L}{2}$, we can use the induction hypothesis that

$$I(B,D,KL{D}^{-(n-1)},r)\le C(\epsilon )B^{\frac{n-2}{n-1}-\epsilon }{(KL{D}^{-(n-1)})}^{\frac{n}{n-1}+\epsilon }{r}^{-\frac{n+1}{n-1}}$$

So we have

$$I(B,D,L,r)\le K\left(D^n\cdot C(\epsilon )B^{\frac{n-2}{n-1}-\epsilon }{(KL{D}^{-(n-1)})}^{\frac{n}{n-1}+\epsilon }{r}^{-\frac{n+1}{n-1}}+DL{r}^{-1}+B^2{r}^{-3}\right)$$

that is

$$I(B,D,L,r)\le C(\epsilon )K^{\frac{2n-1}{n-1}+\epsilon }{D}^{-(n-1)\epsilon }{B}^{\frac{n-2}{n-1}-\epsilon }{L}^{\frac{n}{n-1}+\epsilon }{r}^{-\frac{n+1}{n-1}}+KDL{r}^{-1}+K{B}^2{r}^{-3}$$

Use the conditions above, we have

$$K^{\frac{2n-1}{n-1}+\epsilon }{D}^{-(n-1)\epsilon }{B}^{\frac{n-2}{n-1}-\epsilon }{L}^{\frac{n}{n-1}+\epsilon }{r}^{-\frac{n+1}{n-1}}\le C(\epsilon )B^{\frac{n-2}{n-1}-\epsilon }{L}^{\frac{n}{n-1}+\epsilon }{r}^{-\frac{n+1}{n-1}}$$

$$KDL{r}^{-1}\le C(\epsilon )B^{\frac{n-2}{n-1}-\epsilon }{L}^{\frac{n}{n-1}+\epsilon }{r}^{-\frac{n+1}{n-1}}$$

$$K{B}^2{r}^{-3}\le C(\epsilon )B^{\frac{n-2}{n-1}-\epsilon }{L}^{\frac{n}{n-1}+\epsilon }{r}^{-\frac{n+1}{n-1}}$$

Thus we have $I(B,D,L,r)\le C(\epsilon )B^{\frac{n-2}{n-1}-\epsilon }{L}^{\frac{n}{n-1}+\epsilon }{r}^{-\frac{n+1}{n-1}}$. So we have $|P_r(𝔏)|\le C(\epsilon )B^{\frac{n-2}{n-1}-\epsilon }{L}^{\frac{n}{n-1}+\epsilon }{r}^{-\frac{n+1}{n-1}}$. ∎

References

• [1] Angelo Degree of image of a polynomial map. Note: MathOverflowURL:https://mathoverflow.net/q/63463 (version: 2011-04-29) External Links: https://mathoverflow.net/q/63463, Link Cited by: Solution 6.2.
• [2] A. Basit and A. Sheffer (2014-Dec.) Incidences with $k$-non-degenerate sets and their applications. Journal of Computational Geometry 5 (1), pp. 284–302. External Links: Link, Document Cited by: footnote 11.
• [3] N. Eldredge The lebesgue measure of zero set of a polynomial function is zero. Note: Mathematics Stack ExchangeURL:https://math.stackexchange.com/q/1920527 (version: 2021-07-22) External Links: https://math.stackexchange.com/q/1920527, Link Cited by: footnote 1.
• [4] R. Hartshorne (1977) Varieties. In Algebraic Geometry, pp. 1–59. External Links: ISBN 978-1-4757-3849-0, Document, Link Cited by: Solution 6.1, Solution 6.1.
• [5] M. Kohan $C_1$ And $C_2$ are non-crossing if they are translates of a convex disc. Note: Mathematics Stack ExchangeURL:https://math.stackexchange.com/q/3225611 (version: 2019-05-14) External Links: https://math.stackexchange.com/q/3225611, Link Cited by: footnote 5.
• [6] R. Lidl and H. Niederreiter (1996) Equations over finite fields. In Finite Fields, Encyclopedia of Mathematics and its Applications, pp. 268–346. Cited by: Solution 3.2, Solution 3.2, Solution 8.2.
• [7] G. Martin Polynomial that can be represented as a linear combination. Note: Mathematics Stack ExchangeURL:https://math.stackexchange.com/q/5051406 (version: 2025-03-30) External Links: https://math.stackexchange.com/q/5051406, Link Cited by: footnote 2.
• [8] Z. Nie and A. Y. Wang (2015) Hilbert functions and the finite degree zariski closure in finite field combinatorial geometry. Journal of Combinatorial Theory, Series A 134, pp. 196–220. External Links: ISSN 0097-3165, Document, Link Cited by: Solution 2.9.
• [9] L. A. Szekely (1997) Crossing numbers and hard erdos problems in discrete geometry. Combinatorics, Probability and Computing 6 (3), pp. 353–358. External Links: Document Cited by: footnote 6, footnote 7.

Generated on Sun Aug 24 17:10:26 2025 by LaTeXML