text:
\section{Simple and Simplicial Polyhedra}
\label{sec:simpsimp}

It is a well-known fact \cite[Exerc.~0.1]{GMZ} that a
$d$-\emph{polytope} which is both simple and simplicial is a simplex
or a polygon. Both properties (simplicity as well as simpliciality)
can be viewed as properties of vertex-facet incidences (see
Section~\ref{sec:definitions}). In this section, we generalize the
known result on polytopes to not necessarily bounded $d$-polyhedra
with $d\geq 2$.

\begin{thm}\label{thm:simple_simplicial}
  For $d \geq 2$, every simple and simplicial $d$-polyhedron is a
  simplex or a polygon.  In other words, unbounded simple and
  simplicial polyhedra do not exist.
\end{thm}

Our proof of Theorem \ref{thm:simple_simplicial} is organized into two
parts. The first part shows that the graph $\Gamma_P$ of a simple and
simplicial polyhedron $P$ is either a complete graph or a cycle.  In
the second part, we further deduce that a simple and simplicial
polyhedron has a \emph{circulant} vertex-facet incidence matrix. The
proof of Theorem~\ref{thm:simple_simplicial} is then completed by
showing that no unbounded $d$-polyhedron (with $d\geq 2$) can have a
circulant vertex-facet incidence matrix. Furthermore,
Propositions~\ref{prop:graph_cycle_or_complete} and~\ref{prop:circInc}
yield characterizations of those polyhedra that have circulant
vertex-facet incidence matrices.

\subsection{Graphs of Simple and Simplicial Polyhedra}

Throughout this section, let $P$ be a pointed simple and simplicial
$d$-polyhedron with $n$ vertices and $d\ge2$.  Double counting yields
that $P$ must also have $n$ facets. In particular, we have $n>d$
(since otherwise $P$ would be a cone, which is simple and simplicial
only for $d=1$). We denote by $V_P=\verts{P}$ the set of vertices of
$P$. For $S\subseteq V_P$ let $\inFacs{S}$ be the set of all
facets of $P$ that contain $S$. Recall that (since $P$ is simple) two
vertices $v$ and $w$ of $P$ form an edge if and only if
$\card{\inFacs{\{v,w\}}}=d-1$.

\begin{lem}\label{lem:no_equal_rows}
  Two different facets of $P$ cannot have the same set of vertices.
\end{lem}

\begin{proof}
  Suppose that there are two facets $F_1$ and $F_2$ of $P$ ($F_1\not=
  F_2$) with $\verts{F_1}=\verts{F_2}=:S$. Since $n > d$, and since
  $\Gamma_P$ is connected, there must be a vertex $v \notin S$ that is
  a neighbor of some vertex $w\in S$. Hence, we have
  $\card{\inFacs{\{v,w\}}}=d-1$. Because of $\card{\inFacs{\{w\}}}=d$
  and $F_1,F_2\in\inFacs{\{w\}}\supseteq\inFacs{\{v,w\}}$ this implies
  $F_1\in\inFacs{\{v,w\}}$ or $F_2\in\inFacs{\{v,w\}}$, which in both
  cases yields a contradiction to $v\not\in S$.
\end{proof}

For $S \subseteq V_P$, define $\touchedFacs{S}$ to be the set of those
facets of $P$ that have non-empty intersection with $S$.

\begin{lem}\label{lem:span_of_ones}
  Let $S \subseteq V_P$ with $\card{S}>0$. Then
  $\card{\touchedFacs{S}} \geq \min \{ n,d+\card{S}-1\}$.
\end{lem}

\begin{proof}
  If $\card{\touchedFacs{S}} = n$, then the claim obviously is
  correct. Therefore, assume $\card{\touchedFacs{S}} < n$.  Since
  $\Gamma_P$ is connected, the vertices in $V_P \setminus S = \{z_1,
  \dots, z_{r}\}$ ($r= n-\card{S}$) can be ordered such that $z_{i+1}$
  is adjacent to some vertex of $S_i = S \cup \{ z_1, \dots, z_i \}$
  for each $i \in \{0, \dots, r-1\}$ (additionally, define $S_r = S
  \cup \{z_1, \dots, z_r\}$). Clearly $\card{\touchedFacs{S_i}} \leq
  \card{\touchedFacs{S_{i-1}}}+1$, since vertex $z_i$ has $d-1$ facets
  in common with some vertex in $S_{i-1}$.

  Define $l$ to be the last $i$, such that $\card{\touchedFacs{S_i}} =
  \card{\touchedFacs{S_{i-1}}}+1$, i.e., $l$ is the last index, where we
  encounter a new facet ($l$ is well-defined due to
  $\card{\touchedFacs{S}} < n$). Since this facet must contain $d-1$
  vertices from $V_P\setminus S_l$, we have $r-l \geq d-1$, which
  yields $n-l \geq d+\card{S}-1$.

  Furthermore, we have $\card{\touchedFacs{S}} + l \geq n$, since $S_l$
  intersects all facets. It follows $\card{\touchedFacs{S}} \geq
  n-l \geq d+\card{S}-1$.
\end{proof}

For $S\subseteq V_P$ let $\Gamma_P(S)$ be the subgraph of $\Gamma_P$
induced by $S$.

\begin{lem}\label{lem:full_column_sum}
  Let $S \subset V_P$ with $0<\card{S}\leq d$, such that
  $\Gamma_P(S)$ is connected. Then $\card{\inFacs{S}}=d-\card{S}+1$ holds.
\end{lem}

\begin{proof}
  Since $\Gamma_P(S)$ is a connected subgraph of the connected graph
  $\Gamma_P$ (which has $n>d$ vertices), there is a chain $\emptyset
  \subsetneq S_1 \subsetneq S_2 \subsetneq \ldots \subsetneq S_d$ with
  $S_{\card{S}}=S$, such that $\card{S_i}=i$ and $\Gamma_P(S_i)$ is connected
  for all~$i$.

  For every $1<i\leq d$, the vertex $v$ with $S_i\setminus
  S_{i-1}=\{v\}$ is connected to some vertex $w\in S_{i-1}$. From
  $\card{\inFacs{\{w\}}\setminus\inFacs{\{v\}}}=1$ we infer
  $\card{\inFacs{S_{i-1}}\setminus\inFacs{\{v\}}}\leq 1$, and thus,
  $\card{\inFacs{S_i}}\geq\card{\inFacs{S_{i-1}}}-1$.  Together with
  $\card{\inFacs{S_1}}=d$ (since $P$ is simple) and
  $\card{\inFacs{S_d}}\leq 1$ (by Lemma~\ref{lem:no_equal_rows}), this
  implies $\card{\inFacs{S_i}}=d-i+1$ for all $1\leq i\leq d$.
\end{proof}

The next three lemmas show that $\Gamma_P$ has a very special
structure.

\begin{lem}
  If $\fingr{P}$ contains a cycle $C$ of size $k>d$, then
  $\fingr{P}$ is the cycle $C$ or a complete graph on $n=d+1$ nodes.
\end{lem}

\begin{proof}
  Let $C = ( v_0, \dots, v_{k-1}, v_0 )$ be a cycle of size $k > d$ in
  $\Gamma_P$.  In the following, all indices are taken
  modulo~k.  For $0 \le i \le k-1$ define the set $C_i = \{ v_i,
  \dots, v_{i+d-1}\}$ of size $d$.  Clearly, $\Gamma_P(C_i)$ is
  connected, and, by Lemma~\ref{lem:full_column_sum}, there exists
  exactly one facet $F_i$ with $\inFacs{C_i}=\{F_i\}$.  Due to $k >
  d$, the facets $F_0, \dots, F_{k-1}$ are pairwise distinct. This
  means that $\inFacs{\{v_i\}}=\{F_{i-d+1},\dots,F_i\}$ (since $P$ is
  simple) and $\verts{F_i}=C_i$ (since $P$ is simplicial).  Hence,
  every vertex that is adjacent to one of the nodes $v_0,\dots,
  v_{k-1}$ must be contained in at least one (more precisely, in
  $d-1>0$) of the facets $F_0,\dots, F_{k-1}$, and thus it lies in
  $\{v_0, \dots, v_{k-1}\}$.

  Since $\Gamma_P$ is connected, this means that $n = k$.  For $n=d+1$
  this immediately yields that $\Gamma_P$ is a complete graph on
  $n=d+1$ nodes, while for $n>d+1$ one finds that $\Gamma_P$ is the
  cycle~$C$ (since, in this case,
  $\card{\inFacs{\{v_i\}}\cap\inFacs{\{v_j\}}}=d-1$ if and only if
  $j\equiv i\pm 1\mod k$).
\end{proof}

\begin{lem}
  If $\fingr{P}$ contains a cycle of length $k\leq d$, then
  $\fingr{P}$ is a complete graph on $n=d+1$ nodes.
\end{lem}

\begin{proof}
  Let $\widetilde{C} = (v_0, \dots, v_{k-1}, v_0)$ be a cycle in $\fingr{P}$ of
  size $k\leq d$. For each $i\in\{0,\dots,k-1\}$ define
  $\widetilde{C}_i=\{v_0,\dots,v_i\}$. Taking all indices modulo~$k$, we
  have $|\inFacs{\{v_i,v_{i+1}\}}|=d-1$ for each $i$, and hence, there
  are facets $F_i$ and $G_i$ with
  $$
  \inFacs{\{v_i\}}\setminus\inFacs{\{v_{i+1}\}}=\{F_i\}
  \quad\text{and}\quad
  \inFacs{\{v_{i+1}\}}\setminus\inFacs{\{v_i\}}=\{G_i\}\enspace.
  $$
  It follows that
  \begin{equation}
    \label{eq:Ck-1}
    \inFacs{\widetilde{C}_{k-1}}=\inFacs{\widetilde{C}_0}\setminus\{F_0,\dots,F_{k-1}\}\enspace.
  \end{equation}
  If $\fingr{P}$ is not complete, then $n>d+1$ holds, and we infer
  from Lemma~\ref{lem:span_of_ones} that $\card{\touchedFacs{\widetilde{C}_2}}\geq
  d+2$, which implies $G_0,G_1\not\in\inFacs{\widetilde{C}_0}$ (with $G_0\not=
  G_1$). Due to $\{F_0,\dots,F_{k-1}\}=\{G_0,\dots,G_{k-1}\}$,
  Equation~\eqref{eq:Ck-1} implies
  $$
  \card{\inFacs{\widetilde{C}_{k-1}}}\geq\card{\inFacs{\widetilde{C}_0}}-(k-2)=d-k+2\enspace,
  $$
  contradicting Lemma~\ref{lem:full_column_sum}.
\end{proof}

By the above two lemmas, $\fingr{P}$ cannot contain any cycles, unless
it is complete or a cycle itself. Thus, we are left with the case of
$\fingr{P}$ not containing any cycles at all.

\begin{lem}\label{lem:graph_not_tree}
  $\Gamma_P$ is not a tree.
\end{lem}

\begin{proof}
  Assume $\Gamma_P$ is a tree. Let $v \in V_P$ be a leaf of
  $\Gamma_P$ with $u$ being the unique vertex of $\fingr{P}$ adjacent
  to $v$. Due to
  $\card{\inFacs{\{v\}}\setminus\inFacs{\{v,u\}}}=1$,
  there is one facet that induces a subgraph of $\fingr{P}$ in
  which $v$ is isolated.  This, however, is a contradiction to
  Lemma~\ref{lem:gamma_connected}.
\end{proof}

Altogether this proves the following.

\begin{prp}\label{prop:graph_cycle_or_complete}
  Let $P$ be a simple and simplicial $d$-polyhedron ($d \geq 2$) with
  $n$ vertices.  Then $\Gamma_P$  is an $n$-cycle or a complete
  graph on $n=d+1$ nodes.
\end{prp}

It is worth to mention that one can generalize Proposition
\ref{prop:graph_cycle_or_complete} in the following way. Let $A$ be a
$0/1$-matrix of size $n \times n$ with row and column sums~$d$. Define
a graph $\Gamma_A$ on the columns of $A$, such that two columns are
adjacent if and only if they have exactly $d-1$ ones in common rows.
Then, by the same arguments as above, one can show that the
connectedness of $\Gamma_A$ already implies that $\Gamma_A$ is a cycle
or a complete graph. The only difference in the proof arises in Lemma
\ref{lem:graph_not_tree}. Here one has to prove additionally that, for
each row, the subgraph of $\Gamma_A$ that is induced by the ones in
that row is connected (if $\Gamma_A$ is connected).

\subsection{Circulant Matrices}

We will now exploit Proposition \ref{prop:graph_cycle_or_complete}
to show that every simple and simplicial polyhedron has a very special
vertex-facet incidence matrix.

Let $n,d$ be integers satisfying $1 \leq d \leq n$. The
$(n,d)$-\emph{circulant}~$M(n,d)$ is the $n\times n$-matrix with $0/1$
entries whose coefficients $m_{ij}$ ($i,j\in\{0,\dots,n-1\}$) are
defined as follows:

$$
m_{ij}=
\begin{cases}
  1 & \text{if $j\in\{i,i+1\bmod n,\ldots,i+d-1\bmod n\}$}\\
  0 & \text{otherwise}
\end{cases}
$$

For $d \geq 1$, the $(d+1,d)$-circulant is an incidence matrix of the
$d$-simplex, and for $n \ge 3$, the $(n,2)$-circulant is an incidence
matrix of the ($2$-dimensional) $n$-gon.

\begin{prp}\label{prop:simpsimpcirc}
  A polyhedron~$P$ is simple and simplicial if and only if it has a
  circulant $M(n,d)$ as  a vertex-facet incidence matrix.  In this case,
  $\dim(P)=d$.
\end{prp}

\begin{proof}
For the ``if''-direction of the proof, let $P$ be a polyhedron with a
vertex-facet incidence matrix $M(n,d)$ ($1\leq d\leq n$). The cases
$d=1$ (implying $n\in\{1,2\}$) as well as $d=n$ (implying $d=n=1$) are
trivial. Therefore, let $2\leq d <n$. Obviously, it suffices to show
$\dim(P)=d$. To each row $i \in \{0,\dots,n-1\}$ of $M(n,d)$ there
corresponds a facet $F_i$ of $P$. For $0 \leq j \leq d-1$ define $G_j =
F_0 \cap \dots \cap F_j$. Clearly, $G_j \supseteq G_{j+1}$ holds for $0
\leq j < d-1$.  Due to $\verts{G_{j}} = \verts{F_0} \cap \dots \cap
\verts{F_j}$ it follows $\verts{G_j} \supsetneq \verts{G_{j+1}}$ and
therefore $G_{j} \supsetneq G_{j+1}$. Now $F_0 = G_0 \supsetneq G_1
\supsetneq \dots \supsetneq G_{d-1}$ is a (decreasing) chain of length
$d-1$ in the face poset of $P$. Hence we have $\dim P \geq d$.  Since
each vertex must be contained in at least $\dim P$ facets it follows
that $\dim P \leq d$ (because each vertex of~$P$ is contained in
precisely $d$~facets).

Conversely, let $P$ be a simple and simplicial $d$-polyhedron ($d\geq
1$) with $n$ vertices. The case $d=1$ is checked easily. Thus, assume
$d\geq 2$. By Proposition~\ref{prop:graph_cycle_or_complete},
$\fingr{P}$ either is a complete graph on $n=d+1$ nodes or it is a
cycle. In the first case, every vertex-facet incidence matrix of $P$
is the complement of a permutation matrix, which can be transformed to
$M(n,d)$ by a suitable permutation of its rows.  In the second case,
consider any vertex-facet incidence matrix $A$ of $P$, where the
columns are assumed to be ordered according to the cycle $\Gamma_P$.
Call two positions $(i,j)$ and $(i,k)$ in $A=(a_{fv})$
($f,v\in\{0,\dots,n-1\}$) \emph{mates} if $k \equiv j+1\pmod n$ and
$a_{ij}=a_{ik}=1$. Walking around the cycle $\Gamma_P$, we find that
the total number of mates in $A$ is precisely $n(d-1)$ (because every
edge is contained in precisely $d-1$ facets).  But then, since every
row of $A$ has only $d$ ones (because $P$ is simplicial), it follows
that in each row the ones must appear consecutively (modulo $n$).
Denote by $s(i)$ the starting position of the block of ones in
row~$i$. Because there are no equal rows in $A$ (by Lemma
\ref{lem:no_equal_rows}) we deduce that $s$ defines a permutation of
the rows of $A$ which tells us how to transform $A$ to $M(n,d)$.
\end{proof}

The following result finishes the proof of
Theorem~\ref{thm:simple_simplicial}
(via Proposition~\ref{prop:simpsimpcirc}).

\begin{prp}
\label{prop:circInc}
  If a polyhedron~$P$ has $M(n,d)$ ($2\leq d < n$) as a vertex-facet
  incidence matrix, then $n=d+1$  ($P$ is a $d$-simplex) or $d=2$
  ($P$ is an $n$-gon).
\end{prp}

\begin{proof}
  If $n=d+1$, then $M(n,d)$ is a vertex-facet incidence matrix
  of a $d$-simplex. Hence, by Theorem~\ref{thm:decide}, $P$ cannot be
  unbounded, and thus it must be a $d$-simplex as well. Therefore, in the
  following we will assume $n>d+1$.

  Let us first treat the case $d+1<n<2d-1$.  Consider the facets $F$
  and~$F'$ corresponding to rows~$0$ and~$n-d+1$, respectively.  If we
  identify the vertices of $P$ with the column indices
  $\{0,\dots,n-1\}$ of $M(n,d)$, then the vertex set of the face
  $G=F\cap F'$ is $\{0\}\cup\{n-d+1,\ldots,d-1\}$, where $\{n-d+1,
  \dots, d-1\} \neq \varnothing$ (due to $n<2d-1$). By
  Propositions~\ref{prop:simpsimpcirc}
  and~\ref{prop:graph_cycle_or_complete}, $\fingr{P}$ is an $n$-cycle
  (due to $n>d+1$). Since neither vertex~$1$ nor vertex~$n-1$, which
  are the only neighbors of~$0$ in $\fingr{P}$, are contained in~$G$,
  we conclude that the subgraph of $\fingr{P}$ induced by~$G$ is
  disconnected, which is a contradiction to
  Lemma~\ref{lem:gamma_connected}.

  Hence, we can assume $n\geq 2d-1$. This implies
  $$
  \facvertposet{P}=\SetOf{\{i,\dots,i+s-1\}}{i\in\{0,\dots,n-1\}, s\in\{1,\dots,d\}}
  $$
  (where, again, all indices are to be taken modulo~n), i.e.,
  $\facvertposet{P}$ consists of all (cyclic) intervals of
  $\{0,\dots,n-1\}$ with at least one and at most $d$ elements. We
  will compute the M\"obius function $\mu$ (see
  Section~\ref{sec:unbounded}) on the lattice $\facvertlat{P}$
  (which arises by adding artificial top and bottom elements $\hat{1}$
  and $\hat{0}$ to $\facvertposet{P}$). For each
  $s\in\{1,\dots,d\}$ let $\mu(s)=\mu(\{0,\dots,s-1\})$. Obviously,
  for every $F\in\facvertposet{P}$ with $\card{F}=s$ we have
  $\mu(F)=\mu(s)$.  In particular, one readily deduces $\mu(1)=-1$ and
  $\mu(2)=-(1+2\cdot(-1))=1$. For $3\leq s\leq d$ we then infer (by
  induction) $\mu(s)=-(1+s\cdot(-1)+(s-1)\cdot(+1))=0$. Thus, we finally
  calculate
  $$
  \mu(\facvertposet{P})=\mu(\hat{1})=-(1+n\cdot(-1)+n\cdot(+1))=-1\enspace,
  $$
  which by~\eqref{eq:muEuler} and Theorem~\ref{thm:decide} implies
  that $P$ is bounded (and, hence, an $n$-gon).

  (Alternatively, one could derive from the \emph{Nerve Lemma}
  \cite[Theorem~10.7]{Bj:TopMethods} that $\facvertposet{P}$ is homotopy-equivalent
  to a circle for $n\geq 2d-1$, and thus, $P$ must be a polygon.)
\end{proof}


TITLE: An (elementary?) Question on Weak Derivatives
QUESTION [0 upvotes]: Let $U\subset \mathbb{R}^{n}$ be an open set and $f:U \to \mathbb{R}$ a continuous function which is piecewise $C^{1}$. This is: there is a partition of $U$ by (say, a finite number of) open sets $U_{\alpha}$, each with piecewise $C^{1}$ boundary, such that $f$ restricted to each of these is $C^{1}$.
My question is the following: (when) are the weak derivatives of $f$, $D_{i} f$, given by the piecewise defined functions $g_{i}|_{U_{\alpha}}=D_{x_{i}}(f|_{U_{\alpha}})$? Where can I find a proof if the case?

REPLY [1 votes]: With the exception of some pathological cases, this will usually be true.  Just verify the definition of weak derivative:
$$  \int_U f D_i \varphi dx = \sum_{\alpha} \left( \int_{\partial U_\alpha} f \varphi \nu_i dS - \int_{U_\alpha} \varphi D_i f dx\right)$$
where $\nu_i$ is the $i^{th}$ component of the normal vector to $\partial U_\alpha$.  Then we have
$$ \int_U f D_i \varphi dx = -\int_{U} \varphi D_i f dx + \sum_{\alpha} \int_{\partial U_\alpha} f \varphi \nu_i dS.$$
I would expect the term on the right side to be zero, besides maybe in pathological cases, since each boundary should be shared by two regions and the normal vector $\nu_i$ will be of opposite sign in each region.


TITLE: Given that A and B are sets such that A ⊆ B, write down P(A) − P(B) in a simplified form
QUESTION [1 upvotes]: The question is: Given that A and B are sets such that A ⊆ B, write down P(A) − P(B) in a simplified form
I'm not sure what they mean by simplified form

REPLY [6 votes]: Given: $A \subseteq B$.
$C \in \mathscr{P}(A)$ implies $C \subseteq A$ so $C \subseteq B$, so $C \in \mathscr{P}(B)$. Conclusion : $\mathscr{P}(A) \subseteq \mathscr{P}(B)$.
$\mathscr{P}(B) \setminus \mathscr{P}(A) = \emptyset$ is quite simplified...


TITLE: Prove $f(x)\equiv C$
QUESTION [1 upvotes]: $f(x)\in C[a,b]$.For any $g(x) \in C[a,b]$ ,which has the property that $\int_a^b g(x) dx=0$,$\int_a^b f(x)g(x) dx=0$.
Prove:$f(x)\equiv C$,$C$ is a constant.
I haven't any ideas yet.
I'm thinking about using the Fourier series,would it work?

REPLY [1 votes]: Put $\displaystyle I=\int_a^b f(x)dx$. Then $\displaystyle g=f-\frac{I}{b-a}$ is such that $\displaystyle \int_a^b g(x)dx=0$.
Hence $\displaystyle \int_a^b f(x)g(x)dx=0$ and :
$$\int_a^b (f(x)-\frac{I}{b-a})^2dx=\int_a^b f(x)g(x)dx-\frac{I}{b-a}\int_a^b g(x)dx=0$$
And we are done.

REPLY [0 votes]: I'm thinking about using the Fourier series,is That right?
Without loss of generality，prove: in $[0,l]$，$f(x)\equiv C$.
let $g(x)=f(\mid x\mid)$
use Fourier series,we get：
\begin{aligned}
g(x)&={a_0 \over 2}+\sum_{n=1}^{\infty} a_n \cos {n \pi x \over l}\\
a_0&=\int_{-l}^l g(x) dx \\
a_n&={1 \over l}\int_{-l}^l g(x)\cos {n \pi x \over l} dx\\
&={2 \over l}\int_0^l g(x)\cos {n \pi x \over l} dx
\end{aligned}
It's easy to get $a_n=0$,s.t $g(x)\equiv {a_0 \over 2}$


TITLE: What is the equivalence relation given the equivalence classes?
QUESTION [0 upvotes]: Let $X$ be a set and $A \subset X$ a subset.  What equivalence relation on $X$ would give rise to the equivalence classes $A$ and $\{x\}$ for $x \in X \setminus A$.  I'm unsure how to formulate the equivalence relation $x \sim y$ if ...

REPLY [2 votes]: if...
$x=y$, or, $x$ and $y$ are in $A$.
It could be clarified that you mean $A$ along with all of the singleton subsets of $X\setminus A$ (as opposed to choosing one particular $x$).  For example, you might add a word: "equivalence classes $A$ and all $\{x\}$ for $x\in X\setminus A$."


TITLE: The integral $\int_{-\infty}^{\infty}\frac{1}{R^2+z^2}e^{-\alpha \sqrt{R^2+z^2}}\mathrm{d}z$
QUESTION [3 upvotes]: I need to evaluate the following integral (for a physical application):
$$I=\int_{-\infty}^{\infty}\frac{1}{R^2+z^2}e^{-\alpha \sqrt{R^2+z^2}}\mathrm{d}z, $$
where $\alpha>0$ and $R>0$.
I tried putting it in Mathematica, but it failed. I thought about using the residue theorem. I thought that the only pole inside the upper half of the complex plane should be at $z=iR$ (because $R^2+z^2=(z-iR)(z+iR)$). But when evaluating the residue at the simple pole $z=iR$, I am left with an answer independent of $\alpha$, which does not make sense physically.

REPLY [7 votes]: In this answer, we use the following well-known general results:
$$K_{n}(z)=\frac{\sqrt{\pi}}{\Gamma(n+\frac{1}{2})}(z/2)^n\int_1^{\infty} \frac{e^{-zx}}{(x^2-1)^{1/2-n}}~dx \tag{1}$$
And:
$$\int K_0(z)~dz=\frac{\pi z}{2}(K_0(z)L_{-1}(z)+K_1(z)L_0(z))+C \tag{2}$$
Where $K_n(z)$ is the modified Bessel function of the second kind and $L_n(z)$ is the modified Struve function. These results have been found here on equation (7) and here respectively.

We use differentiation under the integral sign:
$$I(\alpha)=\int_{-\infty}^{\infty} \frac{1}{R^2+z^2}e^{-\alpha\sqrt{R^2+z^2}}~dz$$
$$I'(\alpha)=-\int_{-\infty}^{\infty} \frac{e^{-\alpha\sqrt{R^2+z^2}}}{\sqrt{R^2+z^2}}~dz$$
The second integral can be computed using the substitution $t=\sqrt{R^2+z^2}$ and the substitution $u=t/R$:
$$\begin{align}\int_{-\infty}^{\infty} \frac{e^{-\alpha\sqrt{R^2+z^2}}}{\sqrt{R^2+z^2}}~dz&=2\int_{0}^{\infty} \frac{e^{-\alpha\sqrt{R^2+z^2}}}{\sqrt{R^2+z^2}}~dz\\&=2\int_R^{\infty} \frac{e^{-at}}{\sqrt{t^2-R^2}}~dt\\&=2\int_1^{\infty} \frac{e^{-\alpha Ru}}{\sqrt{u^2-1}}~du  \end{align}$$
Using equation $(1)$ with $n=0$ gives us a very simple result:
$$I'(\alpha)=-2K_0(\alpha R)$$
We can now integrate with respect to $\alpha$, using equation $(2)$. We obtain:
$$I(\alpha)=-\pi\alpha(L_{-1}(\alpha R)K_0(\alpha R)+L_0(\alpha R)K_1(\alpha R))+C$$
Using that $I(0)=\int_{-\infty}^{\infty} \frac{1}{R^2+z^2}~dz=\pi/R$, we obtain that $C=\pi/R$. Thus, the result is:
$$I=\frac{\pi}{R}-\pi\alpha(L_{-1}(\alpha R)K_0(\alpha R)+L_0(\alpha R)K_1(\alpha R))$$
I highly doubt that one can simplify this further.

REPLY [2 votes]: Differentiate w.r.t $\alpha$
Sub $z=R \sinh(x)$
do the integral over x $\int_{\mathbb{R}}dx\exp(-c\cosh(x))=K_0(c)$, $K_0(c)$ is a modified Bessel-function
integrate back w.r.t. $\alpha$
Use  $\tfrac{2}{\pi z}\int dz  K_0(z)= L_0(z)
    K_0(z)+L_{-1}(z)K_1(z)+C$, $L_b(z)$ is a so called Struve
function
Find Integration constant $C$ by noting that the inital integral is clearly $0$ for $\alpha=\infty$

PS: Your contour Approach fails since you didn't take the branchcut $[i,i\infty]$ into account :/


TITLE: What is the Laurent series of $ \exp \! \bigl( - \frac{1}{z} \bigr) $?
QUESTION [4 upvotes]: I’m thinking that I could simply let $ x = - \dfrac{1}{z} $ in the Maclaurin series for $ e^{x} $:
$$
  1 - x + \frac{x^{2}}{2!} - \frac{x^{3}}{3!} + \cdots
= 1 - \frac{1}{z} + \frac{1}{2! z^{2}} - \frac{1}{3! z^{3}} + \cdots.
$$
Is that right?

REPLY [3 votes]: The Taylor series for $e^x$ is
$$
e^x = \sum_{n=0}^{\infty}\frac{x^n}{n!} = 1 + x + \frac{x^2}{2} + \cdots
$$
Now as you have said, let $x = -\frac{1}{z}$. Then we have
$$
e^{-1/z} = 1 - \frac{1}{z} + \frac{1}{2z^2} - \frac{1}{3!z^3} + \cdots = \sum_{n=0}^{\infty}\frac{1}{(-z)^nn!} = \sum_{n=-\infty}^0\frac{(-z)^n}{(-n)!}
$$
where the Laurent series is
$$
\sum_{n=-\infty}^0\frac{(-z)^n}{(-n)!}
$$
since to be a Laurent series we need a principal part $\sum_{n=-\infty}^{-1}$ and an analytic part $\sum_{n=0}^{\infty}$


TITLE: Confusion about magnetisation through current
QUESTION [0 upvotes]: Why are the magnetic domains in the object aligned when the coil that's wrapped around it has current flowing through it. Also why is a magnetic field formed when current is passing through an object?

REPLY [1 votes]: Torque produce by a magnetic field on a small magnetic dipole(M) is M×B right, when the current is introduced automatically a magnetic field is introduced and therefore due to torque all magnetic dipole try to align themselves in direction of magnetic field produced.


TITLE: Calculus 2 infinite series $\frac{1}{3n + 2\cos n}$
QUESTION [2 upvotes]: The series is $\frac{1}{3n + 2\cos n}$ for $n$ from 1 to infinity.

Does the series converge or diverge? State the test applied.

I know $2\cos n$ will oscillate from -2 to 2. Divergence test give me 0 so it's inconclusive. I was suggested to use the limit comparison test. I was told to compare using $\frac{1}{3n}$. After computation the limit as $n$ goes to infinity looks like $\frac{3n}{3n + 2\cos n}$ which is equal to 1, this is what I don't understand: why does it equal 1?
Finally $\frac{1}{3n}$ is a harmonic series (factor the 1/3 out and you are left with $\frac{1}{n}$) which diverges. There fore we conclude the series diverges by limit comparison test.

REPLY [0 votes]: $$\frac1{3n+2\cos n}\sim_\infty\frac1{3n},\quad\text{which diverge.}$$


TITLE: Fourier Coefficients given a periodic function
QUESTION [1 upvotes]: I have been given a function $f\in C_{st}$ which in $[0,\pi]$ is defined as:
$$ f(x)=\frac{x}{4}(2\pi-x)$$
for $0\leq x\leq \pi$. Which is an even function with period $2\pi$. Let $c_n$ be the Fourier coefficients regarding the usual orthonormal system $\{e_n|n\in\mathbb{Z}\}$ for $(C_{st},(\cdot,\cdot)).$ I have to find the Fourier coeffiecients, however, the answer i get for $c_0$ is not right.
$$ c_0=(f,e_0)=\frac{1}{2\pi}\int_{-\pi}^\pi f(x)e^{-i\cdot0\cdot x}dx=\frac{1}{2\pi}\int_0^\pi (\frac{x}{4}(2\pi-x))dx$$
Calculating this integral gives me that $c_0=\frac{\pi^2}{12}$. However, i am told that the answer should be $c_0=\frac{\pi^2}{6}$. What am i doing wrong?

REPLY [1 votes]: You've been given a function which is defined on $ [0, \pi] $, but you're computing its Fourier coefficients by viewing it as a function on $ [-\pi, \pi] $ that vanishes on $ [-\pi, 0] $. These are not equivalent procedures. If you do a Fourier series expansion on the interval $ [0, \pi] $ instead, you'll get the right coefficient out of it.


TITLE: Is there a manifold $X$ such that $H_{1}(X)$ isn't free abelian or trivial and $X$ can be embedded in $\mathbb{R}^3$?
QUESTION [2 upvotes]: I was hoping to get more intuition for homology, but can't exactly see what would a non-free homology group tell us about a space. The simplest example I know is the real projective plane, but that's still not simple enough to give me any insight. If there is no such space, I would be grateful for a hint towards why is this impossible.

REPLY [1 votes]: This is a version of several questions which were asked and answered earlier:

There are no 2-dimensional manifolds $M$ with torsion in $H_1$ embeddable in $R^3$ (see Mariano's answer here and Kevin's answer here).

Also, there are no 3-dimensional manifolds with torsion in $H_1$ homeomorphic to open subsets in $R^3$, see Eric's answer here.


TITLE: What is $\sum_{n=1}^{\infty} n\cdot\left(\frac{1.05}{1.1}\right)^n$?
QUESTION [0 upvotes]: Possible Duplicate:
How can I evaluate $\sum_{n=1}^\infty \frac{2n}{3^{n+1}}$

Hello:  I was solving a problem and I had to compute $$\sum_{n=1}^{\infty} n\cdot\left(\frac{1.05}{1.1}\right)^n .$$  Please, how do I compute this? Are there any general methods for these kinds of problems? Thanks

REPLY [3 votes]: You want to compute $\sum_{n\ge 1}nr^n$, where $|r|<1$. There is a fairly simple formula for this; it can be derived very easily using a little calculus, and with more work using only the formula for the sum of an infinite geometric series.
With calculus. Let $f(x)=\sum_{n\ge 1}x^n$; this is the sum of an infinite geometric series with ratio $x$ and first term $x$, so we know that $$f(x)=\sum_{n\ge 1}x^n=\frac{x}{1-x}\;,\tag{1}$$ provided that $|x|<1$. Now differentiate $(1)$:
$$f\,'(x)=\sum_{n\ge 1}nx^{n-1}=\frac1{(1-x)^2}\;.$$
That sum is almost what you want, and if we multiply by $x$, we’ll have what you want:
$$\sum_{n\ge 1}nx^n=x\sum_{n\ge 1}nx^{n-1}=\frac{x}{(1-x)^2}\;.\tag{3}$$ Substitute $x=\frac{1.05}{1.1}$ into $(3)$, and you’ll get the desired value.
Without calculus. Write out $\sum_{n\ge 1}nr^n$ in a two-dimensional array:
$$\begin{array}{c}
r&+&r^2&+&r^3&+&r^4&+&\dots&=&\frac{r}{1-r}\\
&&r^2&+&r^3&+&r^4&+&\dots&=&\frac{r^2}{1-r}\\
&&&&r^3&+&r^4&+&\dots&=&\frac{r^3}{1-r}\\
&&&&&&r^4&+&\dots&=&\frac{r^4}{1-r}\\
&&&&&&&&\ddots&\vdots&\vdots\\
\\ \hline
r&+&2r^2&+&3r^3&+&4r^4&+&\dots&=&S
\end{array}$$
Summing the bottom row should result in the same total as summing the righthand column, provided that these series actually converge. Thus,
$$\sum_{n\ge 1}nr^n=S=\sum_{n\ge 1}\frac{r^n}{1-r}=\frac1{1-r}\sum_{n\ge 1}r^n\;.$$
Now $\sum_{n\ge 1}r^n$ is again a geometric series, so
$$\sum_{n\ge 1}nr^n=\frac1{1-r}\sum_{n\ge 1}r^n=\frac1{1-r}\cdot\frac{r}{1-r}=\frac{r}{(1-r)^2}\;;$$ this is of course the same formula that we got before.

REPLY [1 votes]: Write $0<\frac{1.05}{1.1}=a<1$ You get:
$$
S_{n}=\sum_{k=0}^{n}ka^k\\
S_{n+1}=S_n + (n+1)a^{n+1} = \sum_{k=0}^{n}ka^k + (n+1)a^{n+1}=\sum_{k=0}^{n}(k+1)a^{k+1}\\
=a \sum_{k=0}^{n}ka^{k}+\sum_{k=0}^{n}a^{k+1}=aS_n+a\sum_{k=0}^{n}a^{k}
$$
Clearly
$$
\sum_{k=0}^{n}a^{k}=\frac{1-a^{n+1}}{1-a}
$$
Rearranging terms we get
$$
S_n = \frac{a(1-a^{n+1})}{(1-a)^2} - \frac{(n+1)a^{n+1}}{(1-a)^2}
$$
No take limit:
$$
\lim_{n \to \infty}S_n=\frac{a}{(1-a)^2}=S
$$
and plug in value for $a$. There are many other ways to find this sum though of course

REPLY [0 votes]: You can use the following approach
$$ \sum_{k=0}^{\infty} x^k = \frac{1}{1-x} \implies \sum_{k=1}^{\infty} k x^{k-1} = \frac{1}{(1-x)^2}\implies\sum_{k=1}^{\infty} k x^{k}= \frac{x}{(1-x)^2}\,, $$
where $|x|<1$. Now, just substitute $x=\frac{1.05}{1.1}\,.$


TITLE: class groups of unramified cyclic p-extensions of imaginary quadratic fields
QUESTION [4 upvotes]: Let $K$ be an imaginary quadratic number field with $p$-Sylow-class group $A(K)$ and $L/K$ be an unramified cyclic extension of $K$ of degree $p$ ($p$ prime). Then I am looking for heuristics on

$ker(N_{L/K}:A(L)\rightarrow A(K))$,

where $N_{L/K}$ is the usual norm map on ideal classes. Numerical data suggest that:
$|KerN_{L/K}|\le p^2$ with high probability. But that is rather unprecise. Are there any more satisfactory known results ?
There is a result by Wittmann who gives some heuristics for cyclic $p$-extensions of $\mathbb{Q}$ and I wonder if one can possibly generalize his ideas to the above scenario.

REPLY [3 votes]: The forthcoming paper "Heuristics for p-class towers of imaginary quadratic fields," by Nigel Boston, Michael Bush, and Farshid Hajir, will answer your question.  In fact, given any finite p-group G, it provides a heuristic for the question "What is the probability that the maximal everywhere-unramified p-extension of K has Galois group isomorphic to G?"
They don't seem to have posted a paper yet, so I'm hesitant to say more about the result without asking their permission, but I'm sure one of them will be happy to send you the preprint or at least tell you what the heuristic is.


TITLE: Let p be a prime number and n an integer such that 1 ≤ n ≤ p. Show that $(p-n)!(n-1)! \equiv (-1)^{n} \mod p$
QUESTION [2 upvotes]: Let p be a prime number and n an integer such that 1 ≤ n ≤ p. Show that.

$$(p-n)!(n-1)! ≡ (-1)^n\mod p.$$

I know it's related to Wilson's theorem ( If p is a prime number, then (p - 1)! ≡ -1 (mod p)) but I don't know, how to prove it?

REPLY [2 votes]: By Wilson´s theorem, $(p-1)!≡-1 \mod p$. That is, $(p-1)(p-2)\dots n(n-1)!≡-1 \mod p$. Now using the $p-n$ congruences modulo $p$
$p-1≡-1$;
$p-2≡-2$;
$\dots$;
$n≡p-(p-n)≡-(p-n)$;
we can substitute in the previous equality and, we obtain$(-1)\cdot(-2)\dots(-(p-n))(n-1)!≡-1 \mod p$, or equivalently,
$(-1)^{(p-n)}(p-n)!(n-1)!≡-1 \mod p$.
This is the same equality as the one in the problem, using that $p$ is odd.


TITLE: Determining the values of $\lambda$ for which the matrix is invertible
QUESTION [4 upvotes]: I'm working on a homework problem and am a little stuck.  The question is:  Determine the values of $\lambda$  for which the matrix $$\begin{pmatrix} \lambda &-1&0\\
-1&\lambda&-1\\
0&-1&\lambda\\
\end{pmatrix}$$
is invertible.
I looked around and one site suggested finding the determinant, which I did:  $|A| = \lambda^3$
What I don't understand is what I'm supposed to do next, now that I have the determinant.

REPLY [2 votes]: The key principle here is that a matrix is invertible if an only if its determinant is non-zero.
We apply this principle here as follows:
Set
$A(\lambda) = \begin{bmatrix} \lambda &-1 & 0 \\ -1 & \lambda & -1 \\ 0 & -1 & \lambda\end{bmatrix}; \tag{1}$
then we have
$\det A(\lambda) = \lambda^3 - 2\lambda; \tag{2}$
thus $\det A(\lambda) = 0$ precisely when
$0 = \lambda^3 - 2 \lambda = \lambda(\lambda^2 - 2); \tag{3}$
the roots of this equation are easily seen to be
$\lambda = 0, \pm \sqrt 2; \tag{4}$
$A(\lambda)$ is thus invertible for all other values of $\lambda$.
Hope this helps.  Cheers,
and as always,
Fiat Lux!!!


TITLE: Can we differentiate equations without changing the solutions?
QUESTION [2 upvotes]: Suppose we have $x^2+4x+3=0$
We differentiate both sides to get $2x+4=0$.
So $x=-2$
But $(-2)^2+4(-2)+3=0$

$4-8+3=-1$ is not equal to $0$.
Which tells that we cannot differentiate equalities. But in many proofs, like in integral calculus, differentiating both sides occurs. So, where is the fallacy?

REPLY [1 votes]: Term by term differentiation of an infinite series identity
$$ \sinh(x) =  \Sigma  \dfrac{x^{2 n -1}} { (2 n-1)!}$$
leads to
$$ \cosh(x) =  \Sigma  \dfrac{x^{2 n }} { (2 n)!}$$
So for all identities it seems to be allowable, but not for functions in general.


TITLE: Why $Z(A)$ is an equivalence relation on $A$?
QUESTION [0 upvotes]: For every algebra $A$, the center $Z(A)$ is a congruence on $A$.
Why is $Z(A)$ an equivalence relation on $A$?

REPLY [1 votes]: Since you referred to the center of an algebra (rather than the center of a group), I believe you mean Definition 5.1 on page 35 of the commutator book.  But by that definition it is obvious that the center is an equivalence relation.
So perhaps your confusion arises from talking about the center of a group rather than a general or "universal" algebra.  In that case, for a group $G$, the center $Z(G)$ is not really a congruence relation of $G$.  However, as a normal subgroup, $Z(G)$ is a single class of a congruence relation of $G$ -- namely, the class containing the identity element of $G$.
In general, each normal subgroup $N$ of a group $G$ can be identified with a congruence relation, $\theta_N$, of $G$.  The congruence classes of $\theta_N$ are the cosets of $N$.  Thus, the lattice of normal subgroups of $G$ is isomorphic to the lattice of congruence relations of $G$. It is because of this identification that a normal subgroup is sometimes loosely referred to as a "congruence" of the group.
See also this answer.


text:
\begin{document}

\author{Ben D. Lund\footnote{lund.ben@gmail.com. Department Of Computer Science, 814 Rhodes Hall, Cincinnati, OH 45221}\\
George B. Purdy\footnote{george.purdy@uc.edu. Department Of Computer Science, 814 Rhodes Hall, Cincinnati, OH 45221}\\
Justin W. Smith\footnote{smith5jw@mail.uc.edu. Department Of Computer Science, 814 Rhodes Hall, Cincinnati, OH 45221} }

\title{A Bichromatic Incidence Bound and an Application}
\maketitle

\begin{abstract}

We prove a new, tight upper bound on the number of incidences between points and hyperplanes in Euclidean d-space.
Given $n$ points, of which $k$ are colored red, there are $O_d(m^{2/3}k^{2/3}n^{(d-2)/3} + kn^{d-2} + m)$ incidences between the $k$ red points and $m$ hyperplanes spanned by all $n$ points provided that $m = \Omega(n^{d-2})$.
For the monochromatic case $k = n$, this was proved by Agarwal and Aronov \cite{AA92}.

We use this incidence bound to prove that a set of $n$ points, no more than $n-k$ of which lie on any plane or two lines, spans $\Omega(nk^2)$ planes.
We also provide an infinite family of counterexamples to a conjecture of Purdy's \cite{EP95} on the number of hyperplanes spanned by a set of points in dimensions higher than 3, and present new conjectures not subject to the counterexample.
\end{abstract}

\section{Introduction}
We consider higher dimensional generalizations of two classical extremal problems from planar combinatorial geometry, and use our upper bound on the number of incidences between points and hyperplanes to obtain a lower bound on the number of planes spanned by a point set.

A point and line are incident if the point is on the line.
Szemer\'edi and Trotter \cite{SzTr83} proved the tight result that there are $O(m^{2/3}n^{2/3} + m + n)$ incidences between $n$ points and $m$ lines in the plane (Lemma \ref{SzemerediTrotter}, below).
Since then, various generalizations of this upper bound have been proved or conjectured - see \cite{PaSh04} for a survey.

One natural generalization is to determine an upper bound on the number of incidences between points and hyperplanes in $\mathbb{E}^d$.
In order to prove an interesting upper bound for this problem, we must restrict the class of admissible arrangements.
Without such a restriction, the trivial upper bound of $mn$ can be attained by placing the $n$ points on a single $(d-2)$-flat that is covered by each of the $m$ hyperplanes.
A number of upper bounds with various restrictions on admissible arrangements have been proved  \cite{EdGuSh90, EdSh90, AA92, BrKn03, ElTo05}.

A hyperplane in $\mathbb{E}^d$ is spanned by a set of points if it passes through $d$ points that do not all lie on a $(d-2)$-flat.
Agarwal and Aronov \cite{AA92} showed that there are $O_d(m^{2/3}n^{d/3} + n^{d-1})$ incidences between $n$ points and $m$ hyperplanes spanned by the points, provided that $m = \Omega(n^{d-2})$.
(The subscript on $O_d$ indicates that the constant implicit in the asymptotic notation depends on $d$).
This problem had been previously considered by Edelsbrunner et. al. \cite{EdGuSh90}, and a construction achieving the asymptotic bound was provided by Edelsbrunner \cite[p. 112]{Ed87}.

In section \ref{sec:BichromaticIncidenceBound}, we show that there are $O_d(m^{2/3}k^{2/3}n^{(d-2)/3} + kn^{d-2} +m)$ incidences between $k$ red points and $m$ hyperplanes if the hyperplanes are spanned jointly by the red points and $n-k$ blue points, provided that $m = \Omega(n^{d-2})$.
In the same section, we provide a construction achieving this asymptotic bound.
This bound is equivalent to Agarawal and Aronov's in the limiting case that all of the hyperplanes are red (i.e., $k = n$).

Although the bichromatic incidence bound is interesting in its own right, our investigation of it is motivated by our interest in a second question:
What is the minimum number of hyperplanes spanned by a set of points?
To obtain a non-trivial answer to this question, some restriction on the point set must be assumed even in two dimensions, since a set of collinear points determines exactly one line.

The specific results we are most interested in extending are the weak Dirac \cite{SzTr83, Be83} and Beck-Erd\H{o}s \cite{Be83} theorems (Lemmas \ref{WeakDirac} and \ref{BeckErdos}, below).

In contrast to the numerous higher dimensional generalizations of the Szemer\'edi-Trotter theorem, there are few extremal results on the number of hyperplanes spanned by a set of points in more than two dimensions.
Hansen proved that a set of points in $\mathbb{E}^d$ that do not all lie on a single hyperplane determines at least one ordinary hyperplane, where an ordinary hyperplane is defined as a hyperplane with all but one of its points on a $(d-2)$-flat \cite{Han65}.
Beck proved that a set of points in $\mathbb{E}^d$, not too many of which lie on any single hyperplane, determines $\Omega_d(n^d)$ hyperplanes \cite{Be83} (Lemma \ref{TwoExtremes}).

Our main result on the number of hyperplanes spanned by a set of points, presented in section \ref{sec:Beck-ErdosR3}, is a three dimensional analog to the Beck-Erd\H{o}s theorem.
We show that a set of points in $\mathbb{E}^3$, no more than $n-k$ of which lie on a plane or any pair of skew lines, determines $\Omega(nk^2)$ planes.

In section \ref{sec:WeakPurdy}, we provide an infinite family of counterexamples to a conjecture of Purdy on the number of hyperplanes spanned by a set of points in $\mathbb{E}^d$ \cite{EP95}, and provide a modified conjecture not refuted by the counterexample.
We also conjecture a generalization of the Beck-Erd\H{o}s theorem that encompasses the three dimensional Beck-Erd\H{o}s analog we prove in section \ref{sec:Beck-ErdosR3}.

\subsection{Theorems in planar combinatorial geometry}
\label{sec:BasicTheorems}

Our proofs in higher dimensions depend on results from planar combinatorial geometry.
Although these theorems were proved in the plane, they apply to points and lines in any dimension since collinear points remain collinear and distinct under projection to a suitable plane.

We use the Szemer\'edi-Trotter incidence bound.
\begin{lemma}[Szemer\'edi, Trotter \cite{SzTr83}]\label{SzemerediTrotter}
There are $O(m^{2/3}n^{2/3} + m + n)$ incidences between $n$ points and $m$ lines in $\mathbb{E}^2$.
\end{lemma}

We also rely on three lower bounds on the number of lines spanned by a set of points in the plane.
The first of these, conjectured independently by Dirac \cite{Dir51} and Motzkin \cite{Mot51}, and proved independently by Szemer\'edi and Trotter \cite{SzTr83} and Beck \cite{Be83}, is known as the weak Dirac theorem.
\begin{lemma}[Szemer\'edi, Trotter, Beck \cite{SzTr83, Be83}]\label{WeakDirac}
A set of $n$ points in $\mathbb{E}^2$ that are not all collinear contains a point incident to $\Omega(n)$ lines.
\end{lemma}

The second result we use on the number of lines spanned by a set of points was conjectured by Erd\H{o}s \cite{Er75, Er81} and proved by Beck. Purdy had previously shown it to be a consequence of the weak Dirac \cite{Pur81}. It is known as the Beck-Erd\H{o}s theorem.
\begin{lemma}[Beck \cite{Be83}]\label{BeckErdos}
A set of $n$ points in $\mathbb{E}^2$ of which at most $n-k$ are collinear determines $\Omega(nk)$ lines.
\end{lemma}

We will refer to the third result on lines spanned by points that we use as Beck's lemma.
It was first stated and proved by Beck, and was used by Beck to prove the Beck-Erd\H{o}s and weak Dirac theorems.
\begin{lemma}[Beck \cite{Be83}]\label{TwoExtremesInE2}
A set of $n$ points in $\mathbb{E}^2$ of which at most $n/100$ are collinear determines $\Omega(n^2)$ lines.
\end{lemma}

\section{Bichromatic incidence bound}
\label{sec:BichromaticIncidenceBound}

\newcommand{\diracC}{\ensuremath{c_{dirac}}}
\newcommand{\hyps}{\ensuremath{\mathcal{H}}}
\newcommand{\hypnum}[1]{\ensuremath{H_{#1}}}
\newcommand{\hyp}[2]{\ensuremath{H^{(#2)}_{#1}}}
\newcommand{\linep}[2]{\ensuremath{L_{#1}^{(#2)}}}
\newcommand{\lines}[1]{\ensuremath{\mathcal{L}}^{(#1)}}
\newcommand{\redinc}[1]{\ensuremath{\mathcal{I}_{R}^{#1}}}
\newcommand{\blueinc}[1]{\ensuremath{\mathcal{I}_{B}^{#1}}}
\newcommand{\redlines}[1]{\ensuremath{\mathcal{L}_{R}^{(#1)}}}
\newcommand{\bluelines}[1]{\ensuremath{\mathcal{L}_{B}^{(#1)}}}

\newcommand{\khypsind}[1]{\ensuremath{k'}}
\newcommand{\nhypsind}[1]{\ensuremath{n'}}
\newcommand{\redhypsind}[1]{\ensuremath{\mathcal{H'}^{(#1)}_{R}}}
\newcommand{\bluehypsind}[1]{\ensuremath{\mathcal{H'}^{(#1)}_{B}}}

\newcommand{\redhyps}{\ensuremath{\mathcal{H}_{R}}}
\newcommand{\redhypsinc}[1]{\ensuremath{\mathcal{H}^{(#1)}_{R}}}
\newcommand{\bluehyps}{\ensuremath{\mathcal{H}_{B}}}
\newcommand{\bluehypsinc}[1]{\ensuremath{\mathcal{I}^{(#1)}_{B}}}
\newcommand{\hypspoint}[1]{\ensuremath{\mathcal{H}^{(#1)}}}
\newcommand{\incds}[2]{\ensuremath{\mathbf{I^d}\left(#1,#2\right)}}
\newcommand{\verts}{\ensuremath{\mathcal{P}}}
\newcommand{\vassigned}[1]{\ensuremath{\mathcal{P}^{(#1)}}}

In this section, we investigate upper bounds on the number of incidences between the vertices of an arrangement of red and blue hyperplanes, and the red hyperplanes of the arrangement.
This is dual to the incidence problem stated in the introduction.

\subsection{Incidences between hyperplanes and vertices of their arrangement}

Our results generalize those of Agarwal and Aronov \cite{AA92}, and Edelsbrunner \cite{Ed87}.
The problem they considered is as follows.

In $\mathbb{E}^d$, given a set $\hyps$ of hyperplanes and a subset $\verts$ of the vertices of their arrangement, let $\mathbf{I^d}(\verts, \hyps)$ denote the number of incidences between $\hyps$ and $\verts$.
Let $\mathbf{I^d}(m,n)$ be the maximum number of incidences over all such sets of $n$ hyperplanes and $m$ vertices of their arrangement.
That is, let
\[\mathbf{I^d}(m, n) = \max_{\substack{|\verts|=m\\
|\hyps|=n}}\mathbf{I^d}(\verts,\hyps).\]

Since each point-hyperplane pair determines at most $1$ incidence, $\mathbf{I^d}(m,n) = O(mn)$.
Edelsbrunner proved that this is tight in the case that $m=O(n^{d-2})$.
\begin{lemma}[Edelsbrunner, \cite{Ed87}]\label{mnBound}
If $d \geq 2$ and $m=O(n^{d-2})$, then
\[\mathbf{I^d}(m,n) = \Theta_d(mn).\]
\end{lemma}

$\mathbf{I^d}(m,n)$ increases monotonically with $m$, so Lemma \ref{mnBound} implies that $\mathbf{I^d}(m,n) = \Omega_d(n^{d-1})$ when $m=\Omega(n^{d-2})$.
Edelsbrunner \cite{Ed87} also showed that $\mathbf{I^d}(m,n) = \Omega_d(m^{2/3}n^{d/3})$ when $m=\Omega(n^{d-2})$.
Agarwal and Aronov proved the corresponding upper bound for these cases \cite{AA92}.
\begin{lemma}[Agarwal, Aronov]\label{AgarwalAronov}
If $d \geq 2$ and $m = \Omega(n^{d-2})$, then
\[\mathbf{I^d}(m,n) = \Theta_d(m^{2/3}n^{d/3} + n^{d-1}).\]
\end{lemma}

\subsection{A bichromatic generalization}

In $\mathbb{E}^d$, given a set $\redhyps$ of red hyperplanes, a set $\bluehyps$ of blue hyperplanes, and a subset $\verts$ of the vertices of their combined arrangement, let $\mathbf{I^d}(\verts, \redhyps, \bluehyps)$ denote the number of incidences between $\redhyps$ and $\verts$.
Let $\mathbf{I^d}(m,k,n)$ be the maximum number of red hyperplane-point incidences over all such sets of $k$ red hyperplanes, $n-k$ blue hyperplanes, and $m$ vertices of their combined arrangement.
That is, let
\[\mathbf{I^d}(m, k, n) = \max_{\substack{|\verts|=m\\
|\redhyps|=k\\
|\bluehyps|=n-k}}\mathbf{I^d}(\verts,\redhyps,\bluehyps).\]

If $k = n$, there are no blue hyperplanes and this is exactly the problem considered by Edelsbrunner, Agarwal and Aronov.

\begin{theorem}\label{mnBichromaticBound}
If $d \geq 2$ and $m = O(n^{d-2})$, then
\[\mathbf{I^d}(m,k,n) = \Theta_d(mk).\]
\end{theorem}
\begin{proof}
The upper bound is trivial.

For the lower bound, take an arrangement of $n$ hyperplanes and $m$ vertices of their arrangement such that the total number of incidences between the hyperplanes and vertices is $\Omega(mn)$.
Lemma \ref{mnBound} implies that such an arrangement exists.
Choose $k$ hyperplanes of the arrangement such that no other set of $k$ hyperplanes is incident to more of the vertices and color them red.
By construction, the average number of incidences between the red hyperplanes and vertices is at least as large as the average number of incidences between all the hyperplanes and the vertices.
Since the average number of incidences between all the hyperplanes and vertices is $\Omega(m)$, the total number of incidences between red hyperplanes and vertices must be $\Omega(mk)$.

\begin{comment}
For the lower bound, we'll use a construction similar to the one used by Edelsbrunner to prove Lemma \ref{mnBound} \cite[p. 110]{Ed87}.

If $d = 2$, the result is trivial since $n^{0} = 1$.
With foresight, define
\[p = \min \left(\lfloor m^{1/(d-2)}\rfloor, \lfloor n/2(d-2) \rfloor \right).\]
For $d > 2$, we will choose $p^{d-2}$ vertices on a $(d-2)$-dimensional grid.
We will use the coordinate system $(x_1, x_2, ..., x_d)$ and provide equations for the hyperplanes $g_i$, with $0 \leq i \leq n-1$.
Define integers $a,b$ such that $i = (a-1)p + b$ with $0 \leq b < p$.
For $0 \leq i < (d-2)p$, set
\[g_i: x_a = b.\]

Notice that these hyperplanes are normal to the $(d-2)$-flat $f:x_{d-1} = x_d = 0$.
The remaining hyperplanes will each contain $f$.
For $(d-2)p \leq i < n$, set
\[g_i: x_{d-1} + ix_d = 0.\]

Since $p \leq \lfloor n/2(d-2)\rfloor$, there are at least $n - (d-2)p \geq n/2$ hyperplanes that each contain all the vertices spanned by the hyperplanes $g_i$.
Color $\min(k,n/2) = \Omega(k)$ of these hyperplanes red.
The hyperplanes $g_i$ collectively determine $p^{d-2} = \Omega_d(m)$ vertices, so the total number of incidences between vertices and red hyperplanes is $\Omega_d(mk)$.
\end{comment}
\end{proof}

\begin{theorem}[Bichromatic incidence bound]\label{BichromaticAgarwalAronov}
If $d \geq 2$ and $m = \Omega(n^{d-2})$, then
\[\mathbf{I^d}(m, k, n) = \Theta_d(m^{2/3}k^{2/3}n^{(d-2)/3} + kn^{d-2} + m).\]
\end{theorem}

If $k=n$ (i.e., there are no blue hyperplanes), then this simplifies to $\Theta_d(m^{2/3}n^{d/3} + n^{d-1} + m)$.
Since the points are vertices of the arrangement, $m = O(n^d)$, so $m = O(m^{2/3}n^{d/3})$.
Substituting, we obtain $\Theta_d(m^{2/3}n^{d/3} + n^{d-1})$, the bound proved by Agarwal and Aronov (Lemma \ref{AgarwalAronov}).

We prove Theorem \ref{BichromaticAgarwalAronov} in two parts.
First, following Agarwal and Aronov \cite{AA92}, we show an upper bound on $\mathbf{I^d}(m,n,k)$, and then, to show this is the best possible, we modify Edelsbrunner's \cite[p113]{Ed87} construction that achieves the upper bound.

\subsection{Proof of the upper bound for Theorem \ref{BichromaticAgarwalAronov}}

\begin{lemma}\label{bichromaticUpperBound}If $d \geq 2$ and $m = \Omega(n^{d-2})$, then
\[\mathbf{I^d}(m,k,n) = O_d(m^{2/3}k^{2/3}n^{(d-2)/3} + kn^{d-2} + m).\]
\end{lemma}

\begin{proof}
In $\mathbb{E}^d$, let $\redhyps$ be a set of $k$ red hyperplanes, and let $\bluehyps$ be a set of $n-k$ blue hyperplanes such that $\redhyps \cap \bluehyps = \emptyset$.
Let $\hyps$ be their combined arrangement.
Let $\verts$ be a subset of the vertices of $\hyps$, each incident to at least one red hyperplane, with $ \left|\verts\right| = m$.

Lemma \ref{SzemerediTrotter} (the Szemeredi-Trotter incidence bound)
does not require the points to be vertices of the arrangement of lines,
so the theorem is true for $\mathbb{E}^2$.
This will be the base case for induction.

Let $P$ be an arbitrary point of $\verts$, and let
$\hypspoint{P} = \{\hyp{1}{P},\hyp{2}{P},\ldots,\hyp{t}{P}\} \subseteq \hyps$
be the set of hyperplanes that contain $P$.
Let $\redhypsinc{P}$ be the set of red hyperplanes that contain $P$.

Place a two dimensional plane $M$ in general position, so that the hyperplanes of $\hypspoint{P}$ intersect $M$ at lines
$\lines{P} = \{\linep{1}{P},\linep{2}{P},\ldots,\linep{t}{P}\}$.
We can place $M$ so that no two members of $\lines{P}$ are parallel.
Let each $\linep{i}{P}$ correspond to hyperplane $\hyp{i}{P}$ and have the same color as $\hyp{i}{P}$.
Let $\redlines{P}\subseteq\lines{P}$ be the red lines, and let $\bluelines{P}\subseteq\lines{P}$ be the blue lines.

Since $P$ is a vertex spanned by the hyperplanes of $\hypspoint{P}$,
the lines of $\lines{P}$ are not all concurrent; however, the red lines of $\redlines{P}$ might be.
If the red lines are concurrent, then there must exist a blue line $\linep{i}{P} \in \bluelines{P}$ that intersects all of the red lines at distinct points.
Otherwise, by the dual weak Dirac there exists a red line $\linep{i}{P} \in \redlines{P}$ and a constant \diracC,
such that $\linep{i}{P}$ intersects at least $\diracC|\redlines{P}|$ other red lines at distinct points.
In either case, there exists a line $\linep{i}{P}$ on $M$ that intersects the lines of $\redlines{P}$ in at least $\diracC|\redlines{P}|$ distinct points,
and so the hyperplane $\hyp{i}{P}$ corresponding to $\linep{i}{P}$ intersects the hyperplanes of $\redhypsinc{P}$ in at least $\diracC|\redlines{P}|=\diracC|\redhypsinc{P}|$ distinct $(d-2)$-flats.
Since $P$ is spanned by $\hyps$, it is also spanned by the intersection of $(d-2)$-flats in $\hyp{i}{P}$.

Assign $P$ to $\hyp{i}{P}$, i.e., let $f(P)=\hyp{i}{P}$.
The process of assignment may be repeated for each point in $\verts$, assigning them to hyperplanes in $\hyps$.

Select an arbitrary hyperplane $\hypnum{i}$ of $\hyps$.
Let $\vassigned{i}$ be the set vertices assigned to hyperplane $\hypnum{i}$.
That is, $\vassigned{i} = \{P \in \verts: f(P) = \hypnum{i}\}$.
Let $m_i = |\vassigned{i}|$.
Let $\redhypsind{i}$ be the set of $(d-2)$-flats formed by the intersection of the hyperplanes of $\redhyps$ with $\hypnum{i}$, and let $\bluehypsind{i}$ be the $(d-2)$-flats formed by the intersection of the hyperplanes of $\bluehyps$ with $\hypnum{i}$.
Let $\khypsind{i} = |\redhypsind{i}|$, and let $\nhypsind{i} = |\redhypsind{i} \cup \bluehypsind{i}|$.

We now have an arrangement, $\redhypsind{i} \cup \bluehypsind{i}$, of $(d-2)$-flats contained in $(d-1)$-dimensional space, $\hypnum{i}$,
that determine a set of points, $\vassigned{i}$.
Note that for a particular $P \in \vassigned{i}$, the number of incidences between $P$ and the $(d-2)$-flats of $\redhypsind{i}$
is at least $\diracC$ times the number of incidences it has with the hyperplanes $\redhyps$.
We apply the inductive hypothesis to determine an upper bound on \incds{\vassigned{i}}{\redhyps},
\begin{equation}
\label{eqn:baa-ind}
\begin{split}
\incds{\vassigned{i}}{\redhyps}& \leqslant
\frac{1}{\diracC}\incds{\vassigned{i}}{\redhypsind{i}}\\
& = \frac{1}{\diracC} O_{d-1}\left(m_i^{2/3}\khypsind{i}^{2/3}\nhypsind{i}^{(d-3)/3} + \khypsind{i}\nhypsind{i}^{d-3} + m_i\right)\\
& = O_d\left(m_i^{2/3}\khypsind{i}^{2/3}\nhypsind{i}^{(d-3)/3} + \khypsind{i}\nhypsind{i}^{d-3} + m_i\right)\\
& = O_d\left(m_i^{2/3}k^{2/3}n^{(d-3)/3} + kn^{d-3} + m_i\right).
\end{split}
\end{equation}

The same logic may be applied to the remaining $n-1$ hyperplanes of $\hyps$.
Since each point $P \in \verts$ is assigned to exactly one \vassigned{i},
\[
\incds{\verts}{\redhyps} = \sum_{i=1}^n\incds{\vassigned{i}}{\redhyps}.
\]

From the upper bound on  $\incds{\vassigned{i}}{\redhyps}$ (inequality \ref{eqn:baa-ind}), it follows that
\[
\incds{\verts}{\redhyps} = O_d\left(\sum_{i=0}^n\left(m_i^{2/3}k^{2/3}n^{(d-3)/3} + kn^{d-3}+m_i\right)\right).
\]

Since each point $P \in \verts$ is in exactly one of the sets $\vassigned{i}$,
we see that $m = \sum_{i=1}^n m_i$.
Since $\varphi(x)=x^{2/3}$ is concave, Jensen's inequality implies
 $\sum_{i=1}^n m_i^{2/3} \leq n^{1/3}(\sum_{i=1}^n m_i)^{2/3}$,
and thus,
\[
\mathbf{I^d}(m,k,n) = O_d\left(m^{2/3}k^{2/3}n^{(d-2)/3} + kn^{d-2} + m\right).
\]
\end{proof}

\subsection{Proof of the lower bound for Theorem \ref{BichromaticAgarwalAronov}}
The upper bound has three terms.
If $m = \Omega(k^2n^{d-2})$, then the $O_d(m)$ term dominates.
If $m = O(k^{1/2}n^{d-2})$, then the $O_d(kn^{d-2})$ term dominates.
Otherwise, the $O_d(m^{2/3}k^{2/3}n^{(d-2)/3})$ term dominates.

We may very easily achieve $1$ incidence for each point, so
\[\mathbf{I^d}(m,k,n) = \Omega(m).\]
Since $\mathbf{I^d}(m,k,n)$ increases monotonically with $m$, Theorem \ref{mnBichromaticBound} immediately implies that if $m = \Omega(n^{d-2})$, then
\[\mathbf{I^d}(m,k,n) = \Omega_d(kn^{d-2}).\]

We will modify a construction presented by Edelsbrunner \cite[p. 112]{Ed87} to demonstrate the third term in the lower bound.
We need the following lower bound  in two dimensions, customarily attributed to Paul Erd\H{o}s:
\begin{lemma}[Edelsbrunner, \cite{Ed87}]\label{E2Construction}
\[\mathbf{I^2}(m,n) = \Omega(m^{2/3}n^{2/3}).\]
\end{lemma}

\begin{lemma}
\[\mathbf{I^d}(m,k,n) = \Omega_d(m^{2/3}k^{2/3}n^{(d-2)/3}).\]
\end{lemma}
\begin{proof}
If $m = \Omega(k^2n^{d-2})$, this follows immediately from the fact that $\mathbf{I^d}(m,k,n) = \Omega(m)$, so we will assume that $m = O(k^2n^{d-2})$.
If $m = O(n^{d-2})$, this follows immediately from Theorem \ref{mnBichromaticBound}, so we will assume that $m = \Omega(n^{d-2})$.
If $k = \Omega(n)$, the conclusion follows immediately from the lower bound established by Edelsbrunner, so we will assume that $n-k = \Omega(n)$.

We will construct a set of hyperplanes $\mathcal{H}$ from the disjoint union of sets $\redhyps, \mathcal{H}_1, ..., \mathcal{H}_{d-2}$, to be defined later.
The set of vertices of $\mathcal{H}$ is $\mathcal{P}$, and we will count the incidences between $\mathcal{P}$ and $\redhyps$.

We will use a coordinate system $(x_1, x_2, ..., x_d)$.

Define
\[p = c_0\left\lfloor m/n^{d-2} \right\rfloor,\]
with $c_0$ to be set later.
Since $m = O(k^2n^{d-2})$, we know that
$p \leq c_1k^2$, for some $c_1$ depending on $c_0$.

The set $\redhyps$ contains $k$ red hyperplanes normal to a plane $\pi$, with $\pi$ defined as
\[\pi: x_1 = x_2 = ... = x_{d-2}=0.\]
The intersection of the arrangement $\mathcal{H}_R$ with $\pi$ is a set of lines $\mathcal{L}_R$ intersecting in a set of points $\mathcal{P}_R$ with $|\mathcal{P}_R| = p$ and $\mathbf{I^2}(\mathcal{L}_R, \mathcal{P}_R) = \Omega(p^{2/3}k^{2/3})$.
Since $p \leq c_1k^2$, Lemma \ref{E2Construction} implies that there exists a constant $c_0$ such that this arrangement is guaranteed to exist; choose $c_0$ accordingly.
Since the hyperplanes of $\mathcal{H}_R$ are normal to $\pi$, the intersection of $\mathcal{H}_R$ with any plane parallel to $\pi$ will be combinatorially equivalent to the arrangement of $\mathcal{L}_R$.

The sets $\mathcal{H}_1, ..., \mathcal{H}_{d-2}$ each contain $\lfloor (n-k)/(d-2) \rfloor$ parallel blue hyperplanes.
Place the sets of hyperplanes so that any $d-2$ hyperplanes, one from each set $\mathcal{H}_1, ..., \mathcal{H}_{d-2}$, intersect in a unique common plane parallel to $\pi$.
Formally, we can define
\[\mathcal{H}_i = \{x_i = j | j=0,1,...,\lfloor (n-k)/(d-2) \rfloor - 1\}\]
for $1 \leq i \leq d-2$.
Since there are $\lfloor (n-k)/(d-2) \rfloor^{d-2}$ ways to choose one hyperplane from each set $\mathcal{H}_1,...,\mathcal{H}_{d-2}$, and each plane forming their intersection accounts for $\Omega(p^{2/3}k^{2/3})$ intersections between vertices of the overall arrangement and the red hyperplanes of $\mathcal{H}_0$, we can conclude that
\[\mathbf{I^d}(\mathcal{P}, \mathcal{H}_R, \mathcal{H}_1 \cup \mathcal{H}_2 \cup ... \cup \mathcal{H}_{d-2}) = \Omega(p^{2/3}k^{2/3}(n-k)^{d-2}) = \Omega(p^{2/3}k^{2/3}n^{d-2}).\]
Here, $|\mathcal{P}| = p\lfloor(n-k)/(d-2)\rfloor^{d-2} = \Theta(m)$.
Since $p^{2/3}k^{2/3}n^{d-2} = \Theta(m^{2/3}k^{2/3}n^{(d-2)/3})$, this proves the theorem.
\end{proof}

Together, the above upper and lower bounds imply Theorem \ref{BichromaticAgarwalAronov}.

\section{Three dimensional analog of the Beck-Erd\H{o}s theorem}
\label{sec:Beck-ErdosR3}

In this section, we prove the following three dimensional analog of the Beck-Erd\H{o}s theorem for points and lines.

\begin{theorem}\label{BeckErdos3}
A set of $n$ points in $\mathbb{E}^3$, of which no more than $n-k$ are on any plane or on any pair of skew lines, spans $\Omega (nk^2)$ planes.
\end{theorem}

\subsection{Planes from incidences}
Our basic strategy is to find $\Omega(nk^2)$ point-hyperplane incidences, and then to apply the following corollary of Theorem \ref{BichromaticAgarwalAronov} to show that the lower bound on point-hyperplane incidences implies a lower bound on hyperplanes.
\begin{lemma}\label{bichromaticConsequence}
Let $\mathcal{P}$ be a set of $n$ points in $\mathbb{E}^d$, and let $\mathcal{K} \subseteq \mathcal{P}$ with $|\mathcal{K}|=k$.
If there are $\Omega(n^{d-2}k^2)$ incidences between points of $\mathcal{K}$ and hyperplanes spanned by $\mathcal{P}$, then there are $\Omega(n^{d-2}k^2)$ hyperplanes spanned by $\mathcal{P}$.
\end{lemma}
\begin{proof}
By the dual of Theorem \ref{BichromaticAgarwalAronov}, there are $O(m^{2/3}n^{(d-2)/3}k^{2/3} + n^{d-2}k + m)$ incidences between $k$ points of $\mathcal{P}$ and the $m$ hyperplanes spanned by $\mathcal{P}$.
There are three cases to consider.

\it Case 1. \rm
\[n^{d-2}k^2 = O(n^{d-2}k).\]
This implies that $k = O(1)$.
Since $O(1)$ points have a total of $\Omega(n^{d-2})$ incidences, some of them must have $\Omega(n^{d-2})$ incidences, so there must be $\Omega(n^{d-2})$ hyperplanes.

\it Case 2. \rm
\[n^{d-2}k^2 = O(m).\]
It immediately follows that $m = \Omega(n^{d-2}k^2)$.

\it Case 3. \rm
\[n^{d-2}k^2 = O((m^{2/3}n^{(d-2)/3}k^{2/3}).\]
Solving for m gives $m=\Omega(n^{d-2}k^2)$.
\end{proof}

\subsection{Combinatorial preliminaries}
It will be helpful to establish two essentially combinatorial results (Corollary \ref{pigeonholeFlats} and Lemma \ref{longLineLemma}) for application in Case 2 of the proof of Theorem \ref{BeckErdos3} (below).
\begin{lemma}[Modified pigeonhole principle]\label{pigeonhole}
Let $0 < c \leq 1$. If $\lceil ck^a \rceil$ discrete objects are allocated to $k$ containers, none of which can contain more than $k^{a-1}$ objects, then at least $\lfloor ck^{a-1}/2 \rfloor$ of the objects must be in each of at least $ck/2$ containers.
\end{lemma}
\begin{proof}
Partition the $k$ containers into two sets:
set $\mathcal{A}$ has the containers with at least $\lfloor ck^{a-1}/2 \rfloor$ objects; set $\mathcal{B}$ has the containers with fewer than $\lfloor ck^{a-1}/2 \rfloor$ objects.
Let $n_a$ be the number of objects in all the containers of $\mathcal{A}$, and let $n_b$ be the number of objects in all the containers of $\mathcal{B}$.

Since no container has more than $k^{a-1}$ objects,
\[n_a \leq |\mathcal{A}|k^{a-1}.\]
Since every member of $\mathcal{B}$ has fewer than $\lfloor ck^{a-1}/2 \rfloor$ objects,
\[\lfloor ck^{a-1}/2 \rfloor|\mathcal{B}| > n_b.\]
Clearly, $n_b = \lceil ck^a \rceil - n_a$ and $|\mathcal{B}| = k - |\mathcal{A}|$, so
\begin{eqnarray*}
\lfloor ck^{a-1}/2 \rfloor(k - |\mathcal{A}|) & > & \lceil ck^a \rceil - |\mathcal{A}|k^{a-1} \\
|\mathcal{A}|k^{a-1} > |\mathcal{A}|(k^{a-1} - \lfloor ck^{a-1}/2 \rfloor) & > & \lceil ck^a \rceil - k\lfloor ck^{a-1}/2 \rfloor \geq ck^a/2.
\end{eqnarray*}
Therefore,
\[ |\mathcal{A}|  >  ck/2.\]
\end{proof}

When we apply this lemma below, the ``objects" in the above lemma are incidences and the ``containers" are points.

\begin{corollary}\label{pigeonholeFlats}
Let $0 < c\leq 1$. If there are at least $ck^a$ incidences between a set of $d$-flats and a set of points, and if no point is incident to more than $k^{a-1}$ $d$-flats, then at least $ck/2$ points must each be incident to at least $\lfloor ck^{a-1}/2 \rfloor$ $d$-flats.
\end{corollary}

This is an immediate consequence of Lemma \ref{pigeonhole}.

\begin{lemma}\label{longLineLemma}
Let $\mathcal{T}$ be a set of $n$ points in $\mathbb{E}^3$ such that no more than $n'$ lie on any plane or pair of lines.
If there is a subset $\mathcal{L} \subset \mathcal{T}$ of at least $n'-k$ collinear points, then
\begin{enumerate}
\item no subset of $\mathcal{T} \setminus \mathcal{L}$ with more than $k$ points is collinear, and
\item no subset of $\mathcal{T} \setminus \mathcal{L}$ with more than $k$ points is on a plane with the line covering $\mathcal{L}$.
\end{enumerate}
\end{lemma}

\begin{proof}
Let $\mathcal{V} \subseteq \mathcal{T} \setminus \mathcal{L}$ with more than $k$ points that is collinear or on a plane with $\mathcal{L}$.
The union of $\mathcal{L}$ and $\mathcal{V}$  will form a set of more than $n'$ points.
\end{proof}

\subsection{Proof of Theorem \ref{BeckErdos3}}

\begin{proof}
Let the full set of $n$ points be $\mathcal{T}$.
A plane or pair of lines that is incident to at least as many points as any other plane or pair of lines exists; we will denote the set of $n-x$ points incident to this plane or pair of lines by $\mathcal{H}$, and denote $\mathcal{T} \setminus \mathcal{H}$ by $\mathcal{X}$.
In other words:
\begin{eqnarray*}
\mathcal{T} & = & \mathcal{H} \cup \mathcal{X} \\
|\mathcal{T}| & = & n \\
|\mathcal{X}| & = & x \geq k \\
|\mathcal{H}| & = & n-x \leq n-k.
\end{eqnarray*}
Since $k \leq x$, it will be sufficient to show that $\Omega(nx^2)$ planes are spanned by $\mathcal{T}$.

\it Case 1. \rm
Suppose that no plane contains more than $\beta_3n$ points of $\mathcal{T}$, where $\beta_3$ is a constant from Lemma \ref{TwoExtremes}.
The following ``two extremes" lemma covers this case.
\begin{lemma}[Beck \cite{Be83}]\label{TwoExtremes}
There are positive constants $\beta_d$ and $\gamma_d$ depending only on the dimension such that any set of $n$ points in $\mathbb{E}^d$ of which fewer than $\beta_d n$ points are on any single hyperplane spans at least $\gamma_dn^d$ hyperplanes, for $d \geq 2$.
\end{lemma}

If $|\mathcal{H}| \leq \beta_3n$, then no plane contains more than $\beta_3n$ points, which is case 1.
For the remaining three cases, we may assume that $|\mathcal{H}| > \beta_3n$.

\it Case 2. \rm
Let $\mathcal{L}$ be the largest set of collinear points in $\mathcal{H}$, and suppose $|\mathcal{L}| = |\mathcal{H}|-x'$ with $x' \leq \min(c_ex/2, \beta_3x/2)$,
where $c_e$ is the constant from Lemma \ref{BeckErdos}.

Let $\Lambda_r$ be the set of lines spanned by $\mathcal{X}$ that do not intersect the line that covers $\mathcal{L}$.

\begin{proposition}\label{RExists}
There is a set of points $\mathcal{R} \subset \mathcal{X}$ with $|\mathcal{R}| = \Omega(x)$ such that each point of $\mathcal{R}$ is incident to $\Omega(x)$ lines of $\Lambda_r$.
\end{proposition}
\begin{proof}
Let $l_t$ be the number of lines spanned by $\mathcal{X}$, let $l_s$ be the number of lines spanned by $\mathcal{X}$ that intersect the line covering $\mathcal{L}$, and let $l_r = |\Lambda_r|$.
In other words,
\[l_r = l_t - l_s.\]

Since $|\mathcal{L}| = |\mathcal{H}| - x'$, Lemma \ref{longLineLemma} implies that no subset of $\mathcal{X}$ larger than $x'$ is collinear.
Since $x' < x/2$, Lemma \ref{BeckErdos} implies that
\[l_t > c_ex^2/2. \]

Lemma \ref{longLineLemma} also implies that no subset of $\mathcal{X}$ larger than $x'$ is on a plane that covers $\mathcal{L}$.
Consequently, no point of $\mathcal{X}$ is on more than $x'-1$ lines spanned by $\mathcal{X}$ that intersect $\mathcal{L}$.
Summing over all $x$ points of $\mathcal{X}$ and dividing by $2$ since each line spanned by $\mathcal{X}$ is incident to at least two points,
\[l_s \leq xx'/2 \leq  c_ex^2/4\]

Since $l_r = l_t - l_s$,
\[l_r > c_ex^2/2 - c_ex^2/4 \geq c_ex^2/4 \geq c_ax^2\]
for some positive constant $c_a$.

Since $l_r = \Omega(x^2)$ and each line of $\Lambda_r$ is on at least two points of $\mathcal{X}$, there must be $\Omega(x^2)$ incidences between $\Lambda_r$ and points of $\mathcal{X}$.
From this, Corollary \ref{pigeonholeFlats} implies that there exists a set of $\Omega(x)$ points each incident to $\Omega(x)$ lines of $\Lambda_r$, completing the proof of Proposition \ref{RExists}.
\end{proof}

Let $P$ be an arbitrary point in $\mathcal{R}$, and let $\Pi_\mathcal{T}$ be the set of planes spanned by $\mathcal{T}$.
Let $\mathbf{I}(P, \Pi_\mathcal{T})$ be the number of incidences between $P$ and $\Pi_\mathcal{T}$.

\begin{proposition}\label{IP}
\[\mathbf{I}(P, \Pi_\mathcal{T}) = \Omega(nx).\]
\end{proposition}
\begin{proof}
Let $\mathcal{A}$ be the set of points on the plane that covers $P$ and $\mathcal{L}$.
Using $P$ as a center, project $(\mathcal{X} \setminus \mathcal{A}) \cup \mathcal{L}$ onto a plane $M$ in general position.
Let $\mathcal{L'}$ be the projection of $\mathcal{L}$ on $M$.
Let $\mathcal{X'}$ be the projection of $\mathcal{X} \setminus \mathcal{A}$ on $M$.
Each point of $\mathcal{L}$ will project to a distinct point on $M$, so
\[|\mathcal{L'}|=|\mathcal{L}| = |\mathcal{H}| - x' \geq \beta_3n - \beta_3x/2 > \beta_3n/2.\]

Since $P \in \mathcal{R}$, Proposition \ref{RExists} implies that $P$ is incident to $\Omega(x)$ lines spanned by $\mathcal{X} \setminus \mathcal{A}$.
Each of these lines will project to a distinct point on $M$, so
\[|\mathcal{X'}| = \Omega(x).\]

Let $l_m$ be the number of lines spanned on $M$ by $\mathcal{L'} \cup \mathcal{X'}$.
Each of these lines corresponds to a plane through $P$, so
\[\mathbf{I}(P,\Pi_\mathcal{T}) \geq l_m.\]

If $|\mathcal{X'}| > \beta_3x/2$, throw away all but $\beta_3x/2$ of the points of $\mathcal{X'}$ to ensure that the line containing $\mathcal{L'}$ has more points of $\mathcal{L'} \cup \mathcal{X'}$ than any other.
Lemma \ref{BeckErdos} implies that
\[l_m = \Omega((|\mathcal{L'}|+|\mathcal{X'}|)|\mathcal{X'}|) = \Omega((\beta_3n/2)\Omega(x)) = \Omega(nx).\]
This completes the proof of Proposition \ref{IP}.
\end{proof}

Repeat the count for each of the $\Omega(x)$ points in $\mathcal{R}$ to get a lower bound on $\mathbf{I}(\mathcal{R}, \Pi_\mathcal{T})$, the number of incidences between the points of $\mathcal{R}$ and planes spanned by $\mathcal{T}$.
\begin{eqnarray*}
\mathbf{I}(\mathcal{R},\Pi_\mathcal{T}) & = & \sum_{P \in \mathcal{R}}\mathbf{I}(P,\Pi_\mathcal{T}) \\
& = & \sum_{i=0}^{|\mathcal{R}|}\Omega(nx) \\
& = & \Omega(nx^2)
\end{eqnarray*}
By Lemma \ref{bichromaticConsequence}, this lower bound implies that $\mathcal{T}$ determines $\Omega(nx^2)$ planes.

Since we have shown that the conclusion of the theorem holds when some line is incident to all but $c_mx = \min(\beta_3x/2, c_ex/2)$ points of $\mathcal{H}$, we may assume that no line is incident to more than $|\mathcal{H}|- c_mx$ points of $\mathcal{H}$ for the remaining cases.

\it Case 3. \rm
Suppose that the points of $\mathcal{H}$ lie in a plane.

Let $l_h$ be the number of lines spanned by $\mathcal{H}$.
Since $|\mathcal{H}| \geq \beta_3n$ and no line is incident to more than $|\mathcal{H}|- c_m x$ points of $\mathcal{H}$, Lemma \ref{BeckErdos} implies that
\[l_h \geq c_e|\mathcal{H}| c_m x \geq c_e c_m \beta_3 nx.\]
Each of the $x$ points in $\mathcal{X}$ is incident to a plane for each line spanned by $\mathcal{H}$, so
\[\mathbf{I}(\mathcal{X},\Pi_\mathcal{T}) \geq c_e c_m \beta_3 nx^2.\]
By Lemma \ref{bichromaticConsequence}, this implies that there are $\Omega (nx^2)$ planes spanned by the point set, proving the theorem for this case.

\it Case 4. \rm
If none of the previous cases hold, then the points of $\mathcal{H}$ must lie on two skew lines.
Let the sets of points on these lines be $\mathcal{L}_0$ and $\mathcal{L}_1$, with
\[|\mathcal{L}_0| \geq |\mathcal{L}_1| \geq c_m x.\]
(If $\mathcal{L}_1 < c_m x$, we'd be in case 2.)
 Since $|\mathcal{H}| \geq \beta_3n$,
\[|\mathcal{L}_0| = |\mathcal{H}| - |\mathcal{L}_1| > \beta_3n/2.\]

Let P be a point in $\mathcal{X}$.
Using $P$ as a center, project the points of $\mathcal{H}$ onto a plane $M$ in general position.
Let $\mathcal{H'}$ be the projection of $\mathcal{H}$ on $M$.
Let $l_{h'}$ be the number of lines spanned by $\mathcal{H'}$.
Since $\mathcal{L}_0$ and $\mathcal{L}_1$ are skew and $P$ is on neither line, the points of $\mathcal{H'}$ will lie on crossing lines on the plane $M$.
The projected lines have at most $1$ point in common, so
\[l_{h'} \geq (|\mathcal{L}_0|-1)(|\mathcal{L}_1|-1) \geq \frac12|\mathcal{L}_0||\mathcal{L}_1| \geq \beta_3 c_m nx/4.\]
Each line spanned by the points of $\mathcal{H'}$ corresponds to a plane through $P$, so
\[\mathbf{I}(P,\Pi_\mathcal{T}) \geq \beta_3 c_m nx/4.\]
The same logic holds for each of the $x$ points in $X$, so
\[\mathbf{I}(\mathcal{X},\Pi_\mathcal{T}) \geq \beta_3 c_m nx^2/4.\]
By Lemma \ref{bichromaticConsequence}, this implies that there are $\Omega (nx^2)$ hyperplanes spanned by the full point set.
\end{proof}

\section{Counterexample to Purdy's conjecture}
\label{sec:WeakPurdy}

In this section, we present an infinite family of counterexamples in dimensions 4 and higher to a conjecture of Purdy's, and we replace it with a modified version that is not subject to our counterexample.

Define the rank of a flat to be one more than its dimension. Purdy's conjecture \cite{Pur81, Pur86, EP95, BrMoPa05} was that, if $n$ is sufficiently large, then any set of $n$ points in $\mathbb{E}^d$, that cannot be covered by a set of flats whose ranks sum to $d+1$, spans at least as many hyperplanes as $(d-2)$-flats.
Gr\"unbaum found counterexamples for $d=3$ with up to 16 points \cite{GrSh84}, but until now no infinite family of counterexamples has been known.
\begin{theorem}\label{OldPurdy}
In $\mathbb{E}^d$, with $d \geq 4$, it is possible to construct a set of $n$ points, that cannot be covered by any set of flats whose ranks sum to $d+1$, that spans $\Theta_d(n^{d-2})$ hyperplanes and $\Theta_d(n^{d-1})$ $(d-2)$-flats.
\end{theorem}
\begin{proof}
We will construct a set of $n = k(d-1)$ points.
First, put $d-1$ lines in general position - we will refer to these lines as the covering lines.
On each of the covering lines, put $k$ points, so that any $d-1$ of these points, one on each of the covering lines, spans a $(d-2)$-flat.

The total rank of the covering lines is $2(d-1)$, which is greater than $d+1$ when $d > 3$.
Since the covering lines are in general position, no more than $m$ lines may be covered by a flat of rank $2m < d+1$, so there is no way to construct a set of flats covering the point set with total rank less than $d+1$.

We will count the number of hyperplanes spanned by the $n$ points by counting the number of hyperplanes that contain $j$ covering lines and summing over all possible values for $j$.

Let $h_j$ be the number of hyperplanes that contain $j$ covering lines.
A hyperplane that contains $j$ lines will contain $d-2j$ points from the remaining covering lines.
$h_j$ is equal to the number of ways to choose the $j$ lines contained in the hyperplane, times the number of ways to choose the $d-2j$ lines that each contribute $1$ point, times the number of ways to choose $1$ point on each of $d-2j$ lines.
In other words,
\[h_j = {d-1 \choose j}{d-1-j \choose d-2j}k^{d-2j}.\]

Let $h$ be the total number of hyperplanes spanned by the point set.
Since there are only $d-1$ covering lines, a hyperplane must contain at least one of the lines.
Since the lines are in general position, no hyperplane will contain more than $\lfloor d/2 \rfloor$ covering lines.
Consequently,
\begin{align*}
h &= \sum_{j} h_j \\
&= \sum_{1 \leq j \leq \lfloor d/2 \rfloor}{d-1 \choose j}{d-1-j \choose d-2j}k^{d-2j}.\\
\text{Since $k = \Theta_d(n)$,} \\
&= \sum_{1 \leq j \leq \lfloor d/2 \rfloor}\Theta_{d,j}(n^{d-2j}) \\
&= \Theta_d(n^{d-2}).\\
\end{align*}

We will proceed in a similar manner to count the number of $(d-2)$-flats spanned by the point set.

Let $g_j$ be the number of $(d-2($-flats that contain $j$ covering lines.
A $(d-2)$-flat that contains $j$ lines will contain $d-1-2j$ points from the remaining lines.
$g_j$ is equal to the number of ways to choose $j$ lines contained in the $(d-2)$-flat, times the number of ways to choose $d - 1 - 2j$ lines that each contribute $1$ point, times the number of ways to choose $1$ point on each of the $d-1-2j$ lines.
In other words,
\[g_j = {d-1 \choose j}{d - 1 - j \choose d - 1 -2j}k^{d-1-2j}.\]

Let $g$ be the total number of $(d-2)$-flats spanned by the point set.
Since there are $d-1$ covering lines, a $(d-2)$-flat may be spanned by one point from each line.
Since the lines are in general position, no $(d-2)$-flat will contain more than $\lfloor (d-1)/2 \rfloor$ covering lines.
Consequently,
\begin{align*}
g &= \sum_j g_j \\
&= \sum_{0 \leq j \leq \lfloor (d-1)/2 \rfloor}{d-1 \choose j}{d-1-j \choose d - 1 - 2j}k^{d-1-2j} \\
&= \sum_{0 \leq j \leq \lfloor (d-1)/2 \rfloor}\Theta_{d,j}(n^{d-1-2j}) \\
&= \Theta_d(n^{d-1}).\\
\end{align*}

\end{proof}

In place of the disproved conjecture, we propose the following related conjectures.

We say that a set of points is $r$-degenerate if it can be covered by any set of flats (of nonzero dimension) whose dimensions add up to less than $r$.
\begin{conjecture}[Modified weak Purdy]\label{higherWeakDirac}
A set of $n$ points in $\mathbb{E}^d$, that is not $d$-degenerate, contains a point incident to $\Omega(p)$ hyperplanes, where $p$ is the number of $(d-2)$-flats spanned by the set.
\end{conjecture}

Using a similar hypothesis, we conjecture a generalization of the Beck-Erd\H{o}s theorem that embraces our theorem in three dimensions as a special case.

\begin{conjecture}\label{higherBeckErdos}
A set of $n$ points in $\mathbb{E}^d$, having no $d$-degenerate subset of more than $n-k$ points, spans $\Omega(nk^{d-1})$ hyperplanes.
\end{conjecture}

\section{Acknowledgments}
We would like to thank Ryan Anderson for several helpful comments and suggestions.
We would also like to thank an anonymous referee for pointing out an error in the  proof of what is now Theorem \ref{BichromaticAgarwalAronov}, and for significant help with the presentation.

\bibliographystyle{IEEEtran}
\bibliography{HyperplanesSpannedByPointArrangements}

\end{document}

config: arxiv