TITLE: Does time stop in black holes?
QUESTION [11 upvotes]: I was going through Hawking's incantations on black holes, where black holes get defined as follows:
Black Hole: A region of spacetime from which the escape velocity exceeds the velocity of light.
I am told that nothing in this universe can have a speed greater than that of light. By Einstein's theory, if black holes actually do have escape velocity greater than the speed of light, this should mean that time in the black hole has stopped completely. In the center of a black hole is a gravitational singularity, a one-dimensional point which contains a huge mass in an infinitely small space, where density and gravity become infinite and space-time curves infinitely, and where the laws of physics as we know them cease to operate. Although supermassive black holes do not usually indulge in the process of moving about the universe, smaller black holes do. I have read from various sources that these black holes move at an appreciable speed comparing with light. So my question here is about the increase in mass and density of the black hole further.
By Einstein's equation, the density of the point where the gravitational singularity has been developed and the mass of the black hole should constantly be increasing. Does this imply that at one time, the black hole should grow vast enough to swallow the entire universe and after the "spaghettification" all the mass of the universe gets stored at the infinitely small point with infinite density?
What I further do not understand is, is that how do black holes grow in mass? In my opinion, by swallowing stars, asteroids, etc., the size of black holes should remain constant and the mass of the point where the singularity is developed should be increased. I have also read that when two black holes crash into each other, their gravitational fields combine to create an even stronger gravitational field.
In this case, are the black holes superposing on each other by pure constructive interference?

REPLY [9 votes]: "if black holes actually do have escape velocity greater than the speed of light, this should mean that time in the black hole has stopped completely"
What it means is that the time axis has twisted round so far that the entire future of an event on the event horizon points entirely into the black hole. You can't escape from the black hole for the same reason you can't escape from the future.
Time doesn't stop at the event horizon. If you fall into a black hole, time continues as normal for you as you pass the event horizon. From the point of view of somebody outside, if you try to join up the time and space coordinates valid a long way away from point to point, as you get closer the flow of time diverges and it looks like time 'stops'. But this is just a peculiarity of the choice of coordinates. It's the same as saying time 'stops' for a ray of light - but we commonly cross the paths of light rays without anything odd happening.
In fact, you can get event horizons without black holes. If a rocket accelerates in a straight line at a constant rate, it gets closer and closer to the path of a particular ray of light. An observer on the rocket can never see anything that happens at the origin after this particular ray of light, as the light from any such event can never catch up to the accelerating observer - it is an event horizon. The diagram here shows the paths of observers with increasing accelerations, and how they all approach a particular diagonal line representing a light ray from the origin. Time for the rocket-propelled observer is shown by the fan of lines through the origin, that go to infinity as the diagonal is approached. An observer on the rocket looking back sees the stationary observer's time apparently 'stop' as their own time continues on to infinity. Of course, time doesn't stop for the stationary observer - they pass through the event horizon without noticing a thing. It's just a peculiarity of the coordinate system of the accelerated observer.
This is an expected consequence of the equivalence principle - that gravity and acceleration look locally the same. The accelerated rocket observers correspond to stationary observers hovering a fixed distance outside a black hole. The stationary observers watching the rocket correspond to a freefall observer falling into the black hole. The spacetime diagram for the Rindler coordinates of uniform acceleration look almost exactly like the Kruskal-Szekeres diagram for a black hole. (Note for the picky, the spacing of the lines in the two diagrams is not quite the same. Rindler 'artificial gravity' goes like $1/r$, not $1/r^2$.) Static observers hovering outside the hole follow the hyperbolic paths in the right-hand quadrant. The event horizon of the black hole is the diagonal lines crossing in the middle. A freefalling observer crosses the event horizon of the black hole like the static observer crosses the event horizon of a uniformly accelerating rocket - simply passing from the past into the future. Once past, he can never move fast enough to recross the line and meet up with the observer on the hyperbola, without exceeding c. Event horizons criss-cross every point in space and time - they're just light rays.
However time does stop at the singularity at the centre of the black hole. The history of particles falling in just stop when they hit it. General relativity predicts the curvature goes to infinity, and can no longer say what happens next.


TITLE: Open sets in $\mathbb{R}$ and $\mathbb{R^2}$
QUESTION [0 upvotes]: I have two questions of open sets in $\mathbb{R}$ and $\mathbb{R^2}$, which come from Rudin's Real and Complex Analysis:

He wrote: "If $X$ is a metric space and if $\tau$ is the collection of all sets $E\subset X$ which are arbitrary open balls, then $\tau$ is a topology". Then he concluded: "in the real line $\mathbb{R}$ a set is open iff it is a union of segments $(a,b)$". I don't understand why he can conclude that, because $\tau$ is not the only topology in $\mathbb{R}$.
I need an explanation for the statement "Every open set $V$ in the plane is a countable union of rectangles with sides parallel to the axes". Why the rectangles, not the open discs, and why countable?

Thanks in advance.

REPLY [1 votes]: For the first problem, there is only one topology on $\mathbb{R}$, and hence on $\mathbb{R}^n$, which is useful to the study of analysis and that is the Euclidean topology.  Yes there are other topologies you can induce on the real number line, but that doesn't mean that they're all metrizable.  The most interesting constructions of continuity, and especially differentiability occur when considering the Euclidean topology.
For the second, if $U \subseteq \mathbb{R}^2$ is open consider the union of all boxes of the form $(a_1, b_1) \times (a_2,b_2) \subseteq U$ where $a_1,b_1, a_2, b_2 \in \mathbb{Q}$.  This forms a countable union of boxes and if $p \in U$  then there is a ball of radius $\epsilon>0$ such that $B_\epsilon(p) \subseteq U$.  If $p = (p_1,p_2)$ then consider the box $\left (p_1 - \frac{\epsilon}{\sqrt{2}}, p_1+\frac{\epsilon}{\sqrt{2}} \right ) \times \left (p_2 - \frac{\epsilon}{\sqrt{2}}, p_2 + \frac{\epsilon}{\sqrt{2}} \right )$.  Now if $q$ is inside this box then
$$
d(p,q) \;\; <\;\; \sqrt{\frac{\epsilon^2}{2} + \frac{\epsilon^2}{2}} \;\; =\;\; \epsilon
$$
where the inequality is due to the fact that if $q = (q_1,q_2)$ then $|p_i - q_i| < \frac{\epsilon}{\sqrt{2}}$ for each $i$.  We therefore have that $q \in B_\epsilon(p)$ hence the box is fully contained in $U$.  This proves that $U$ is equal to the countable union of boxes with rational coordinates properly contained in $U$.


TITLE: Proving a combinatorial identity
QUESTION [0 upvotes]: Prove the following identity combinatorially:
$\sum_{k=0}^m \binom{m}{k} \binom{n+k}{m} = \sum_{k=0}^m \binom{m}{m-k} \binom{n}{k}2^k$

REPLY [1 votes]: Imagine two towers, the left one with $m$ levels and the right one with $n$ levels.  We want to put one-way ladders between the towers, such that each ladder connects a single level of the left tower to a single level of the right tower.  Ladders are not allowed to cross each other--i.e. ladder $i+1$ connects levels of the two towers which are strictly higher than those connected by ladder $i$.  How many ways can we do this?
One way to count the arrangements of ladders is to pick $k$ levels from both towers to be connected.  By the no-crossing requirement for the ladders, the $i$-th highest level of each tower are connected to each other, and there are two ways to run each ladder.  So the number of ways to have $k$ ladders is $\binom{m}{k}\binom{n}{k}2^k$.  Summing over all possible numbers of ladders gives the right hand side of the desired expression.
Another way to count the arrangements of ladders is to first pick $m-k$ levels of the left tower that will have outgoing ladders (rather than incoming ladders or no ladders).  Then of the $n$ levels on the right tower and the $k$ unselected levels on the left tower, you choose $m$ of them, with the following interpretation:

Levels selected on the left tower are those that have no ladders to them.
Levels selected on the right tower are those that do have ladders going to them.

Any levels on the left tower that are not among the original $m-k$ levels nor among the later $m$ levels will have incoming ladders.
You can convince yourself that this procedure uniquely identifies all possible ways of stringing ladders between the two towers, with $m-k$ ladders outgoing from the left tower.  The number of ways to do this is $\binom{m}{m-k}\binom{n+k}{m} = \binom{m}{k}\binom{n+k}{m}$.  Summing over all $k$ gives the left hand side of the desired expression.


TITLE: Proving something is NOT a tensor
QUESTION [1 upvotes]: I need to show that $\frac{\partial}{\partial x^i}v^{j}(x)$ is not a tensor.
Here $v^i(x)$ is a vector field. I tried writing down the tensor transformation like this:
$$\frac{\partial}{\partial{x'^{i'}}}v'^{j'}(x')=\frac{\partial x^i}{\partial x'^{i'}} \frac{\partial x'^{j'}}{\partial x^j} \frac{\partial}{\partial x^i}v^{j}(x)$$
And thus I think this looks like a tensor transformation is supposed to look. I've likely done something incorrectly, could someone please give me a hint here on what I'm doing wrong?

REPLY [1 votes]: What you went wrong is that you don't write the derivation correctly. What you must do is this
$$
\frac{\partial v^{j'}}{\partial x^{i'}} = \frac{\partial}{\partial x^{i'}} v^{j'} = \underbrace{\frac{\partial x^i}{\partial x^{i'}} \frac{\partial}{\partial x^i}}_\text{by chain rule} \underbrace{\Bigg( \frac{\partial x^{j'}}{\partial x^j} v^j   \Bigg) }_\text{by transf.rule for $v^{j'}$} = \dots (\text{proceed})
$$
which is by chain rule and tensor transformation rule $\textbf{for}$ $v^{j'}$.  Proceed by yourself and find out why its not a tensor.


TITLE: Why is there no direct relationship between angle and side length in a triangle?
QUESTION [2 upvotes]: The answer might be quite obvious here but it's something I've been thinking over for a while as I've been going through study of trigonometry. Why, as an angle increases, does the side length corresponding to this angle not increase proportionally?
I'm aware that there is the sine rule used to describe this ratio, a/sin(A) = b/sin(B) = c/sin(C), just wondering why this is?

REPLY [0 votes]: Interesting question!
When you increase an angle by moving the side(s), I believe you keep their length(s) unchanged. Otherwise, it is independent of the angle.
Now recall the Cosine Theorem:
$$c^2=a^2+b^2-2ab\cos{C}.$$
When the angle $C$ is close to $0$, then $\cos{C}$ will be close $1$ and almost maximum, hence maximum value is subtracted which makes $c^2$ minimum.
When the angle $C$ starts to increase from almost $0$, the value of $\cos{C}$ starts to decrease, hence smaller value is subtracted which makes $c^2$ greater.
When the angle $C$ goes over $90^o$, the value of $\cos{C}$ becomes negative, which means the cosine term is added and it keeps making $c^2$ greater.
In conclusion, as an angle changes, the opposite side also changes by the Cosine Theorem.


TITLE: Who is $\operatorname{Hom}_{\mathbb{Z}}(\mathbb{Z}^m,\mathbb{Z}^n)$ isomorphic to?
QUESTION [0 upvotes]: The problem is:

Who is $\operatorname{Hom}_{\mathbb{Z}}(\mathbb{Z}^m,\mathbb{Z}^n)$ isomorphic to? (where $\operatorname{Hom}_{\mathbb{Z}}(\mathbb{Z}^m,\mathbb{Z}^n)=\{f:\mathbb{Z}^m\to\mathbb{Z}^n\mid f  \text{ homomorphism  of $\mathbb{Z}$-modules}\}$)

REPLY [0 votes]: Hint:
Every $\mathbb{Z}$-linear map $$f:\mathbb{Z}^m\rightarrow\mathbb{Z}^n$$
can be expressed as a matrix, with entries $a_{i,j}\in\mathbb{Z}$. How many choices do you have for $a_{i,j}$?


TITLE: Capacitance of a single charged plate?
QUESTION [6 upvotes]: Lets say we have a single plate that has a charge of $+Q$ on it. A plate with charge $-Q$ is infinite distance away. Will the plate with $+Q$ have a capacitance associated with it? Why or why not? I was thinking that because the distance between the plates is infinity, the capacitance is zero, but according to my TA, that is not the case. There is always some sort of "absolute" capacitance for the plate with $+Q$ (a capacitance will exist between the plate and air?). Can someone help me out in understanding this?

REPLY [0 votes]: Both good answers. Note that the Earth has a self-capacitance by the same arguments. The Earth carries a net charge and really does have a capacitance. Remember that capacitance is defined in terms of the work that you must do to take a charge from one plate to the other. Two charged objects are involved. Even if the plates are nearly an infinite distance apart you still will have to do some work to, say, move a positive charge from the negative plate to the positive plate. The electric field due to the destination plate's positive charges will produce a repelling force that you will have to work against to move the test charge. This after all what we mean by potential difference. That is, work done to move a unit charge between two points. Very close to either charged plate the electric field only depends upon the charge density on that part of the plate and is not directly dependent upon the shape or location of the second plate. The proximity of the second plate may affect the value of this charge density. In idealized parallel plate capacitors the field happens to be uniform throughout between the plates. But this local field is always there in all geometries and results in a finite capacitance. C=Q/V. You can always calculate self-capacitance of anything by simply moving a second plate, or rock, or sphere to infinity and do the work calculation.


TITLE: Is the set $I$ in the axiom of infinity often interpreted to be an actual infinite set?
QUESTION [2 upvotes]: After some discussion on philosophy stackexchange I wanted to know what some set theorists consider the infinite set that the axiom of infinity posits to exists.
Question
Do most, or you if you're a set theorist reading this question, set theorists believe that the infinite set $I$ in the axiom of infinity believe that $I$ is a completed infinite set or just a potentially infinite set?
This question is important to me, because I've been wondering how most mathematicians can believe that the set $\mathbb{N}$ is a completed infinite set without the presupposition that actual infinite sets exist. Then I began reflecting on the axiom of infinity, which would provide the mathematician a starting point to begin working on deductions concerning actual infinite sets if this axiom concerns actual infinite sets.
Another reason I'm asking is because I know that if a mathematician is a constructivist or intuitionist, then the axiom of infinity is used as an axiom in their set theory, and I believe this is possible if they interpret that $I$ is a potentially infinite set.
Lastly, and I don't know if it's possible to answer this question, but when Zermelo first proposed the axiom of infinity, did he have in mind that $I$ is an actual infinite set or did he withhold any claims as to whether or not it was an actual or potential infinity?
I'm sorry in advance if this question is not suitable for this stackexchange, but my prior discussion on philosophy stackexchange has led me to confusion as to whether or not $I$ can be interpreted as an actual or potential infinite set, so I was curious to know what some or most mathematicians, especially ones who have no problem with actual infinite sets, consider $I$ to be with respect to the infinite.
So what is $I$ to you?

REPLY [1 votes]: Looking in Gregory H. Moore's book "Zermelo's Axiom of Choice", one can find a brief history of the axiom of infinity (pp. 154--155).
Its roots lie with Bolzano, who argued the existence of an infinite set (via a somewhat-diagonal argument, like the Euclidean proof of the infinitude of primes); Dedekind later reformulated this into what we know now as "Dedekind-infiniteness"; and several others have formulated this in one way or another. However, the foundations of mathematics were still shaping, and a lot of this won't pass the test of modern rigor. Zermelo, however, was different, and postulated the axiom by formalizing exactly what it means for a set of "repeated singletons" to exist.
It seems probable that Zermelo had the natural numbers in mind, since at this point Peano's postulates already existed, and so modeling the natural numbers as $0=\varnothing$ and $n+1=\{n\}$ seemed like a natural thing to do. And Zermelo's axiom of infinity essentially postulated the existence of the natural numbers as a set using this modeling.
The modern formulation of Infinity, however, comes in later, when we think about ordinals, and $\omega$ or $V_\omega$ in the von Neumann hierarchy. To a set theorist, "the infinite set" is by all means $\omega$, which is also the natural numbers for all useful purposes in the context of set theory.
As far as the terms "potential" and "completed" or "actual", I think that you're mixing several philosophical approaches here. In the context of real analysis, sets are not of interest, and only real numbers and functions (or sequences) are of interest. Those are, naively, given by various constructions, and you can ask whether or not something is unbounded. In other words, does a function attain arbitrarily high values? If so, it can be seen as potentially infinite. However every valid input has to return a real number, so it cannot be infinite. Therefore "potential infinity" works just fine.
In set theory, however, we take a fixed universe, and argue over it (using what basic assumptions we made on this universe, e.g. a model of $\sf ZF$ or $V=L$ or whatever). So when we look at an infinite set whose existence is guaranteed by the axiom of infinity, we do not look at it as something "to be constructed in parts", but rather something which already exists. We assumed the axiom, and derived (using existential instantiation) the existence of said set. We can prove that this set is also infinite in any "reasonable" definition of infinite, as far as the universe we work inside cares to admit. Which is why we all have the tacit agreement "yes, this set is infinite".


TITLE: Which partial sum estimates $\sum_{n=1}^{\infty} \frac{(-1)^{(n+1)}*n!}{n^{n}}$ with an error of at most four hundredths (.04)?
QUESTION [0 upvotes]: I think I have to somehow use this formula for truncating error:
Let $\bigg(a_{n} \bigg)_{n=1}^{\infty}$ be a decreasing sequence of positive numbers with $\lim_{n\to\infty} a_{n} = 0$.
Then the alternating series $\sum_{n=1}^{\infty} (-1)^{(n+1)}*a_{n}$ converges. Furthermore, the $jth$ truncation error satisfies the inequality
$E_{j} < a_{j + 1}$
The same results hold for $\sum_{n=1}^{\infty} (-1)^{n}*a_{n}$
I don’t understand any of this
Please help
Thank you

REPLY [0 votes]: A proof of the alternating series criterion which you use can e.g. be found at the bottom of this page


text:
\begin{document}
\pagenumbering{arabic}

\title{Distinct Distances: Open Problems and Current Bounds}

\author{
Adam Sheffer\thanks{California Institute of Technology, Pasadena, CA,
{\sl adamsh@gmail.com}.}
}

\maketitle

\begin{abstract}
We survey the variants of Erd\H os' distinct distances problem and the current best bounds for each of those.
\end{abstract}

\section{Introduction}
Given a set $\pts$ of $n$ points in $\RR^2$, let $D(\pts)$ denote the number of distinct distances that are determined by pairs of points from $\pts$. Let $D(n) = \min_{|\pts|=n}D(\pts)$;
that is, $D(n)$ is the minimum number of distinct distances that a set of $n$ points in $\RR^2$ can determine.
In his celebrated 1946 paper \cite{erd46}, Erd\H os derived the bound $D(n) = O(n/\sqrt{\log n})$.
More specifically, Erd\H os showed that a $\sqrt{n} \times \sqrt{n}$ integer lattice determines $\Theta(n/\sqrt{\log n})$ distinct distances (for more details, see Section \ref{sec:structure}).
Though almost 70 years have passed since Erd\H os considered this lattice structure, no configuration that determines an asymptotically smaller number of distinct distances was discovered.

For the celebrations of his 80th birthday, Erd\H os compiled a survey of his favorite contributions to mathematics \cite{erd96}, in which he wrote
 \begin{quotation}\em ``My most striking contribution to geometry is, no doubt, my problem on the number of distinct distances. This can be found in many of my papers on combinatorial and geometric problems."
 \end{quotation}

After 64 years and a series of increasingly larger lower bounds, Guth and Katz \cite{GK15} derived the bound $D(n) = \Omega(n/\log n)$, almost matching the current best upper bound (a comprehensive study of the previous bounds can be found in \cite{GIS11}).\footnote{See also William Gasarch's webpage: \url{http://www.cs.umd.edu/~gasarch/erdos_dist/erdos_dist.html}} To derive this bound, Guth and Katz developed several novel techniques, relying on tools from algebraic geometry, 19th century analytic geometry, and more.
Notice that a small gap of $O(\sqrt{\log n})$ remains between the current best lower and upper bounds.

\begin{problem} \label{pr:main}
Find the exact asymptotic value of $D(n)$.
\end{problem}

Since the problem is almost completely solved, one might wonder what is the purpose of this document.
The answer is that there are many challenging variants of the distinct distances problem that are still wide open (many of those posed by  Erd\H os).
For some of these variants, such as the ones presented in Section \ref{sec:structure}, even after several decades of work hardly anything non-trivial is known.
This document is meant to be dynamic, keeping track of the current best bounds and conjectures concerning the various distinct distances variants.

\ignore{Papers that study problems from the set that is surveyed in the first part of Section \ref{sec:rest} (i.e., problems that are still open) contain phrases such as ``Our ignorance in this area is really shocking!" \cite{EHP89} and ``It is rather frustrating that I got nowhere with..." \cite{erd87}.}

The main part of this survey is partitioned into six sections, each discussing a different family of problems. Section \ref{sec:structure} discusses the structure of planar point sets that determine a small number of distinct distances. Section \ref{sec:rest} surveys problems in which a planar point set is constrained in some manner. Section \ref{sec:HighD} considers distinct distances in higher dimensions. Section \ref{sec:subset} discusses subsets of points that determine every distance at most once.
Section \ref{sec:kl} surveys another family of restricted point sets, in which every subset of $k$ points determines at least $l$ distinct distances. Finally, Section \ref{sec:additional} presents problems that do not into fit any of the other sections.

For those who are only interested in the ``main" problems, it is the personal view of the author (and likely of others) that currently the most challenging/interesting distinct distances problems are Problem \ref{pr:OnLine} of Section \ref{sec:structure} and Problem \ref{pr:Rd} of Section \ref{sec:HighD}.
Another great collection of open problems related to distinct distances can be found in \cite[Sections 5.3 -- 5.6]{BMP05}.

A more general version of Problem \ref{pr:main} asks whether every planar point set $\pts$ contains a point that determines many distinct distances with the other points of $\pts$ (e.g., see Erd\H os \cite{erd87}). More formally, what is the minimum value $\hd(n)$, such that for every set $\pts$ of $n$ points in $\RR^2$ there exists a point $p \in \pts$ that determines at least $\hd(n)$ distinct distances with the other points of $\pts$?
A simple upper bound is $\hd(n) \le D(n) = O(n/\sqrt{\log n})$.
However, Guth and Katz's bound does not immediately imply a matching lower bound for $\hd(n)$.
The current best lower bound, obtained by Katz and Tardos \cite{KT04}, is $\hd(n) = \Omega(n^{(48-14e)/(55-16e)})\approx \Omega(n^{0.864})$.

\begin{problem} \label{pr:mainPnt}
Find the asymptotic value of $\hd(n)$.
\end{problem}

\section{The structure of point sets with few distinct distances} \label{sec:structure}

In this section we discuss characterizing the point sets that determine a small number of distinct distances.
This seems to be the family of problems for which we know the least; even after decades of studying them, hardly anything is known.
We say that a set $\pts$ of $n$ points in the plane is \emph{optimal} if $D(\pts) = D(n)$.
Since the asymptotic value of $D(n)$ is still unknown, we consider sets $\pts$ of $n$ points that satisfy $D(\pts)=O(n/\sqrt{\log{n}})$, and refer to such sets as \emph{near-optimal}.
All the point sets in this section are planar.

\begin{figure}[h]

\centerline{\placefig{grids}{0.9\textwidth}}
\vspace{-1mm}

\caption{\small \sf (a) An integer lattice.
(b) A lattice that can be obtained from (a) either by rotation and uniform scaling, or by removing from (a) every point whose coordinates sum to an odd number.
(c) A triangular lattice (of equilateral triangles).}
\label{fi:grids}
\vspace{-2mm}
\end{figure}

Erd\H os asked whether every optimal (or near-optimal) set ``has lattice structure" \cite{erd86}.
To make this question clearer, let us first consider some of the known near-optimal sets.
In the introduction we already mentioned that the $\sqrt{n} \times \sqrt{n}$ integer lattice (e.g., see Figure \ref{fi:grids}(a)) determines $O(n/\sqrt{\log n})$ distinct distances. This was observed by Erd\H os, who noticed that this is an immediate corollary of the following theorem from number theory.

\begin{theorem} \label{th:LandRam} {\bf (Landau-Ramanujan \cite{BR95,BMO11,Land08})}
The number of positive integers smaller than $n$ that are the sum of two squares is $\Theta(n/\sqrt{\log n})$.
\end{theorem}

Every distance in the $\sqrt{n} \times \sqrt{n}$ integer lattice is the square root of a sum of two squares between 0 and $n$. Thus, Theorem \ref{th:LandRam} implies that the number of distinct distances in this case is $\Theta(n/\sqrt{\log n})$.

The above implies that the $\sqrt{n} \times \sqrt{n}$ integer lattice is a near-optimal set.
More generally, for any integer $c \ge 1$, every $n$ point subset of the $c\sqrt{n} \times c\sqrt{n}$ integer lattice is a near-optimal set (since we can still apply Theorem \ref{th:LandRam} in such cases), and so are translations, rotations, and uniform scalings of such lattices.
For example, the lattice in Figure \ref{fi:grids}(b) can be obtained either by rotating and scaling the $\sqrt{n} \times \sqrt{n}$ integer lattice, or by removing from the $2\sqrt{n} \times 2\sqrt{n}$ integer lattice every point whose coordinates sum to an odd number.

We can further generalize the above. For any integer $r>1$, we define the rectangular lattice
\[ {\mathcal L}_r = \{ (i,j\sqrt{r}) \ \mid \ i,j\in\ZZ \quad \text{and} \quad  1 \le i,j \le \sqrt{n} \}. \]

The points of any such ${\mathcal L}_r$ span $\Theta(n/\sqrt{\log n})$ distinct distances (e.g., see \cite{Sblog14}).
By applying various transformations to these rectangular lattices, we get more near-optimal lattices. For example, the triangular lattice, which corresponds to the vertices in a tiling of equilateral triangles (e.g., see Figure \ref{fi:grids}(c)), can be obtained by taking a rectangular lattice and removing every other vertex.
After obtaining optimal sets for a few small values of $n$, Erd\H os and Fishburn \cite{EF96} conjectured that, for infinitely many values of $n$, there is an $n$-point subset of the triangular lattice that is optimal (that is, not just near-optimal).

For now, hardly anything is known regarding Erd\H os's conjecture that every near-optimal set has a lattice structure.
As a first step, Erd\H os \cite{erd86} suggested to determine whether every near-optimal point set contains $\Omega(\sqrt{n})$ points on a line, and thus most of the set can be covered by a small number of lines. Since this also appears to be quite difficult, Erd\H os asked whether there exists a line with $\Omega(n^\varepsilon)$ points of the set. Embarrassingly, even this weaker variant remains open.

\begin{problem} \label{pr:OnLine} {\bf (Erd\H os \cite{erd86})}
Prove or disprove: For a sufficiently small $\varepsilon>0$, every near-optimal point set contains $\Omega(n^\varepsilon)$ points on a common line.
\end{problem}

The current best bound is that for every near-optimal set $\pts$ of $n$ points, there exists a line $\ell$ such that $|\ell\cap\pts| = \Omega(\log n)$ (e.g., see \cite{Sblog14b}).
A recent result \cite{LSdZ15} states that for every near-optimal set $\pts$ of $n$ points and $0 < \alpha \le 1/4$, either there exists a line or a circle that contains $n^{\alpha}$ points of $\pts$, or there exist $n^{8/5-12\alpha/5-\eps}$ distinct lines that contain $\Omega(\sqrt{\log n})$ points of $\pts$. Thus, one way to solve Problem \ref{pr:OnLine} might be to prove that for any point set $\pts$ with  many lines that contain $\Omega(\sqrt{\log n})$ points of $\pts$ (and $\pts$ being near optimal), there exists a line containing $\Omega(n^{\eps})$ points of $\pts$.

Sheffer, Zahl, and de Zeeuw \cite{SZZ13} considered the complement problem --- proving that no line can contain many points of a near-optimal set. Specifically, they proved
that for every near-optimal set $\pts$ of $n$ points, every line contains  $O(n^{7/8})$ points of $\pts$. This bound was recently improved to  $O(n^{43/52})$ in \cite{RRNS15}.

\begin{problem} \label{pr:OnLine2}
Prove or disprove: For every near-optimal point set $\pts$and $\varepsilon>0$, every line contains $O(n^{0.5+\varepsilon})$ points of $\pts$.
\end{problem}

In Section \ref{sec:rest} we mention a result by Pach and de Zeeuw \cite{PZ13}, implying that if a set of $n$ points is contained in a constant-degree curve, then these points span $\Omega(n^{4/3})$ distinct distances, unless the curve contains a line or a circle.
That is, for every near-optimal set $\pts$ of $n$ points, any constant degree algebraic curve that does not contain lines and circles contains  $O(n^{3/4})$ points of $\pts$.
In \cite{SZZ13}, it is also proved that for every near-optimal set $\pts$ of $n$ points, every \emph{circle} contains  $O(n^{5/6})$ points of $\pts$.
By combining these three results, we obtain that for every near-optimal set $\pts$ of $n$ points, every constant-degree algebraic curve contains  $O(n^{43/52})$ points of $\pts$.

\begin{problem} \label{pr:OptimalCurves}
Prove or disprove: For every near optimal set $\pts$ of $n$ points and $\varepsilon>0$, every constant-degree curve contains $O(n^{0.5+\varepsilon})$ points of $\pts$.
\end{problem}

\section{Constrained sets of points} \label{sec:rest}

In this section we consider variants of the distinct distances problem where the point sets are constrained in some way. The current best bounds for these problems are listed in Table \ref{ta:sec2}; see Figure \ref{fi:sec2} and the text below for an explanation of the notation used in the table.
Unless stated otherwise, the point sets in this section are planar.

\begin{table}[h]
\begin{center}
\caption{The current best bounds for constrained sets of points.\label{ta:sec2}}
\vspace{2mm}

\begin{tabular}{|c|c|c|}
\hline
{\textbf {Variant}} & {\textbf {Lower bound}} & {\textbf {Upper bound}} \\
\hline\hline
$D_{\text{no3}\ell}(n)$  & $\displaystyle \lceil (n-1)/3\rceil$ (Szemer\'edi) & $\displaystyle \lfloor n/2\rfloor$ \cite{erd46} \\ \hline
$\hd_{\text{no3}\ell}(n)$  & $\displaystyle \lceil (n-1)/3\rceil$ (Szemer\'edi) & $\displaystyle \lfloor n/2\rfloor$ \cite{erd46} \\ \hline
$\hd_{\text{conv}}(n)$  & $\left(\frac{13}{36}+\frac{1}{22701}\right)n +O(1)$ \cite{Dum06,NPPZ11} & $\displaystyle \lfloor n/2\rfloor$ \cite{erd46} \\ \hline
$D_{\text{gen}}(n)$  & $\Omega(n)$ (trivial) & $\displaystyle n2^{O(\sqrt{\log n})}$ \cite{EFPR93} \\ \hline
$\hd_{\text{gen}}(n)$  & $\lceil (n-1)/3 \rceil$ (trivial) & $n-O(1)$ (trivial) \\ \hline
$D_{\text{para}}(n)$  & $\Omega(n)$ (trivial) & $\displaystyle O(n^2/\sqrt{\log n})$ \cite{Dum08} \\ \hline
$D_{\text{lines}}(n)$  & $\Omega(n^{4/3})$ \cite{SS13} & $\displaystyle O(n^2/\sqrt{\log n})$ \cite{Elek99} \\ \hline
$D_{\text{curves}}(n)$  & $\Omega(n^{4/3})$ \cite{PZ13} & $\displaystyle O(n^2/\sqrt{\log n})$ \cite{Elek99} \\ \hline

\end{tabular}
\end{center}
\vspace{-\baselineskip}
\end{table}

\begin{figure}[h]

\centerline{\placefig{sec2b}{0.92\textwidth}}
\vspace{-1mm}

\caption{\small \sf (a) The hierarchy of the constrained point sets in Section \ref{sec:rest}. Every arrow goes from a constrained problem to its generalization. (b) The vertices of a regular 10-gon.}
\label{fi:sec2}
\vspace{-2mm}
\end{figure}

\paragraph{General and convex position.} We begin with a set of problems that ask for exact bounds, instead of asymptotic ones; that is, where the ``fight" is for the best constant of proportionality. The hierarchy between the different types of constraints that are presented in this part is depicted in Figure \ref{fi:sec2}(a).
Denote by $D_{\text{no3}\ell}(n)$ the minimum number of distinct distances that can be determined by a set of $n$ points, no three of which are collinear (that is, $D_{\text{no3}\ell}(n) = \min_{|\pts|=n}D(\pts)$, where the minimum is taken over all sets of $n$ points containing no three collinear points).
Notice that the vertices of a regular $n$-gon, such as the set depicted in Figure \ref{fi:sec2}(b), satisfy this property and determine $\lfloor \frac{n}{2}\rfloor$ distinct distances, implying $D_{\text{no3}\ell}(n) \le \lfloor \frac{n}{2}\rfloor$. The current best lower bound, due to Szemer\'edi (communicated by Erd\H os in \cite{Erd75}; the proof can also be found in \cite[Chapter 13]{PA95}), is $D_{\text{no3}\ell}(n) \ge \lceil \frac{n-1}{3}\rceil$.
Szemer\'edi also conjectured that $D_{\text{no3}\ell}(n) = \lfloor \frac{n}{2}\rfloor$; see \cite{erd87,EHP89}.

\begin{problem} \label{pr:No3}
Find the exact value of $D_{ \text{\em no3}\ell}(n)$.
\end{problem}

As before, let $\hd_{\text{no3}\ell}(n)$ denote the maximum number satisfying that for any set $\pts$ of $n$ points, no three of which are collinear, there exists a point $p\in \pts$ such that there are at least $\hd_{\text{no3}\ell}(n)$ distinct distances between $\pts$ and $\pts\setminus\{p\}$.

\begin{problem} \label{pr:No3Pnt}
Find the exact value of $\hd_{\text{\em no3}\ell}(n)$.
\end{problem}

It can be easily noticed that the regular $n$-gon configuration implies $\hd_{\text{no3}\ell}(n) \le \lfloor \frac{n}{2}\rfloor$, and Szemer\'edi's bound for $D_{\text{no3}\ell}(n)$ also remains valid for $\hd_{\text{no3}\ell}(n)$. Thus, the current best bounds for Problems \ref{pr:No3} and \ref{pr:No3Pnt} are identical (as opposed to the case of Problems \ref{pr:main} and \ref{pr:mainPnt}).

Szemer\'edi's proof is so simple and elegant that it is hard to resist stating it here.
\begin{lemma}\label{le:no3}
$\hd_{\text{\em no3}\ell}(n) \ge \lceil \frac{n-1}{3}\rceil$
\end{lemma}
\begin{theProof}{\!\!}
Consider a set $\pts$ of $n$ points, no three of which are collinear. Let $x$ denote the minimum number satisfying that every point $p\in \pts$ determines at most $x$ distinct distances with the points of $\pts\setminus\{p\}$.

Let $T = \{(a,p,q)\in \pts^3 \mid |ap|=|aq|\}$, where $a,p,q$ are three distinct points and where $(a,p,q)$ and $(a,q,p)$ are counted as the same triple. The proof is based on double counting $|T|$, and we begin by deriving an upper bound for it. Given a pair of points $p,q\in\pts$, the triplet $(a,p,q)$ is in $T$ if and only if $a$ is on the perpendicular bisector of the segment $pq$. By the assumption, each such perpendicular bisector contains at most two points of $\pts$, which implies
\begin{equation}\label{eq:SzUp}
|T| \le 2 \binom{n}{2} = n(n-1).
\end{equation}

For the lower bound, notice that for every point $p\in\pts$, the points of $\pts\setminus\{p\}$ are contained in at most $x$ concentric circles around $p$. We denote these circles as $C_{p,1},\ldots,C_{p,x}$ and set $n_{p,i} = |C_{p,i} \cap \pts|$. Notice that $\sum_{i=1}^xn_{p,i} = n-1$ for every $p\in\pts$. By the Cauchy-Schwarz inequality, we have $\sum_{i=1}^x n_{p,i}^2 \ge \frac{1}{x}(n-1)^2$. This in turn implies

\begin{align} |T| = \sum_{p\in\pts}\sum_{i=1}^x \binom{n_{p,i}}{2} = \frac{1}{2}\sum_{p\in\pts}\sum_{i=1}^x (n_{p,i}^2-n_{p,i}) &\ge \frac{1}{2}\sum_{p\in\pts} \left( \frac{1}{x}(n-1)^2 - (n-1)\right) \nonumber \\
&= \frac{n(n-1)(n-1-x)}{2x}. \label{eq:SzLw}
\end{align}

Combining \eqref{eq:SzUp} and \eqref{eq:SzLw} immediately implies the assertion of the lemma.
\end{theProof}

Although no progress has been made with Problems \ref{pr:No3} and \ref{pr:No3Pnt} for several decades, more recent advances have been obtained for more restricted variants of them.
Similarly to $D_{\text{no3}\ell}(n)$, let $D_{\text{conv}}(n)$ denote the minimum number of distinct distances that can be determined by a set of $n$ points in (strict) convex position. Let $\hd_{\text{conv}}(n)$ denote the maximum number satisfying that for any set $\pts$ of $n$ points in convex position, there exists a point $p\in \pts$ such that there are at least $\hd_{\text{conv}}(n)$ distinct distances between $\pts$ and $\pts\setminus\{p\}$.

By considering the regular $n$-gon once again, we notice that $D_{\text{conv}}(n) \le \lfloor \frac{n}{2}\rfloor$ and that $\hd_{\text{conv}}(n) \le \lfloor \frac{n}{2}\rfloor$. Already in his 1946 paper, Erd\H os \cite{erd46} conjectured that $D_{\text{conv}}(n) = \lfloor \frac{n}{2}\rfloor$. This was proven by Altman \cite{Alt63,Alt72}, which led Erd\H os to suggest the stronger conjecture $\hd_{\text{conv}}(n) = \lfloor \frac{n}{2}\rfloor$.
Since for any set of points in convex position no three points can be collinear, we have $\hd_{\text{conv}}(n) \ge \hd_{\text{no3}}(n) \ge \lceil \frac{n-1}{3}\rceil$. In 2006, Dumitrescu \cite{Dum06} derived the improved bound $\hd_{\text{conv}}(n) \ge \lceil \frac{13n-6}{36}\rceil$. Recently, the slightly improved bound $\hd_{\text{conv}}(n) \ge \left(\frac{13}{36}+\frac{1}{22701}\right)n +O(1)$ was obtained by Nivasch, Pach, Pinchasi, and Zerbib \cite{NPPZ11}.

\begin{problem} \label{pr:conv}
Find the exact value of $\hd_{\text{\em conv}}(n)$.
\end{problem}

We say that a set of points is in \emph{general position} if no three points are collinear and no four points are cocircular. Denote by $D_{\text{gen}}(n)$ the minimum number of distinct distances that can be determined by a set of $n$ points in general position. The convex $n$-gon configuration is not in general position, and it is in fact unknown whether $D_{\text{gen}}(n) = \Theta(n)$ or not. The current best upper bound $D_{\text{gen}}(n) = n2^{O(\sqrt{\log n})}$ was derived by Erd\H os, F\"uredi, Pach, and Ruzsa \cite{EFPR93}. This bound is obtained by  considering a very different construction: taking an integer grid $G$ in a $d$-dimensional space (where $d$ is roughly $\sqrt{\log n}$), considering a subset $G'$ of the points of $G$ that lie on a common sphere, and projecting $G'$ on a generic plane. The generic projection guarantees that the resulting planar set is in general position, while the integer-grid-on-a-sphere structure implies a relatively small number of distinct distances.
For an easy lower bound, notice that $D_{\text{gen}}(n) \ge D_{\text{no3}}(n) = \Omega(n)$.

\begin{problem} \label{pr:gen}
Find the asymptotic value of $D_{\text{\em gen}}(n)$.
\end{problem}

Erd\H os \cite{erd87} also suggested to study the maximum number $\hd_{\text{\em gen}}(n)$ satisfying that for any set $\pts$ of $n$ points in general position, there exists a point $p\in \pts$ such that $\{p\}\times\pts$ determines at least $\hd_{\text{gen}}(n)$ distinct distances. Consider a point set $\pts$ in general position and a point $p\in \pts$. If $p$ has a distance of $d$ from four other points of $\pts$, then each of these four points is incident to the circle whose center is $p$ and radius is $d$, contradicting the general position assumption. Thus, a trivial lower bound is $\hd_{\text{\em gen}}(n) \ge \lceil (n-1)/3 \rceil$. No non-trivial bound is known for $\hd_{\text{\em gen}}(n)$ (neither a lower nor an upper bound), and when discussing the problem, Erd\H os \cite{erd87} wrote ``It is rather frustrating that I got nowhere with\ldots".

\begin{problem} \label{pr:gen}
Find the exact value of $\hd_{\text{\em gen}}(n)$.
\end{problem}

The point configuration that implies $D_{\text{gen}}(n) = n2^{O(\sqrt{\log n})}$ spans many duplicate vectors. This led to denoting by $D_{\text{para}}(n)$ the minimum number of distinct distances determined by a set of $n$ points in general position that do not determine any parallelograms.
Erd\H os, Hickerson, and Pach \cite{EHP89} asked whether $D_{\text{para}}(n)= o(n^2)$. This was recently confirmed by Dumitrescu \cite{Dum08}, who proved $D_{\text{para}}(n)= O(n^2/\sqrt{\log n})$ by considering, for prime $n$, the point set
\[ \left\{ (i,j) \mid i=0,1,\ldots,(n-1)/4, \ j= i^2 \hspace{-2mm}\mod n \right\}. \]
No bound better than the trivial $D_{\text{para}}(n)= \Omega(n)$ is known.
\begin{problem} \label{pr:para}
Find the asymptotic value of $D_{\text{\em para}}(n)$.
\end{problem}

We conclude this section with a conjecture by the author of this survey.
\begin{problem}
Prove or disprove: Let $\pts$ be a set of $n$ points, such that no two distinct pairs of points of $\pts$ have the same perpendicular bisector. Then for every $\eps>0$, we have $D(\pts)=\Omega(n^{2-\eps})$.
\end{problem}

\begin{figure}[h]

\centerline{\placefig{TwoLines}{0.7\textwidth}}
\vspace{-1mm}

\caption{\small \sf Two lines with $O(n)$ distinct distances.}
\label{fi:TwoLines}
\vspace{-2mm}
\end{figure}

\paragraph{Points on curves.}
We move to a different family of constrained point sets, where the points are restricted to being contained in a given curve.

Let $\pts_1$ and $\pts_2$ be two sets of $n$ points each, such that the points of $\pts_1$ (resp., $\pts_2$) lie on a line $\ell_1$ (resp., $\ell_2$). Let $D(\pts_1,\pts_2)$ denote the number of distinct distances between the pairs of $\pts_1\times\pts_2$ (that is, only distinct distances between points on different lines are considered).
When the two lines are either parallel or orthogonal, the points can be arranged such that $D(\pts_1,\pts_2) = \Theta(n)$; for example, see Figure \ref{fi:TwoLines}.
Purdy conjectured that if the lines are neither parallel nor orthogonal then $D(\pts_1,\pts_2) = \omega(n)$  (e.g., see \cite[Section 5.5]{BMP05}). Let us denote as $D_{\text{lines}}(n)$ the minimum number of distinct distances in such a scenario.
Elekes and R\'onyai \cite{ER00} proved Purdy's conjecture, though without deriving any specific superlinear lower bound. Later, Elekes \cite{Elek99} showed that $D_{\text{lines}}(n) = \Omega(n^{5/4})$.
Recently, Sharir, Sheffer, and Solymosi \cite{SS13} proved $D_{\text{lines}}(n) = \Omega(n^{4/3})$.
More generally, they derived the bound $\Omega(\min\{n^{2/3}m^{2/3},m^2,n^2\})$ for the asymmetric case where one line contains $n$ points and the other $m$ points (another recent asymmetric result, which is subsumed by the bound from \cite{SS13}, was derived by Schwartz, Solymosi, and de Zeeuw \cite{SSZ12}).
Elekes \cite{Elek99} also observed the upper bound $D_{\text{lines}}(n) = O(n^2/\sqrt{\log n})$.

\begin{problem} \label{pr:lines}
Find the asymptotic value of $D_{\text{\em lines}}(n)$.
\end{problem}

Generalizing Problem \ref{pr:lines}, we consider the minimum number of distinct distances between two sets of $n$ points, each on a constant degree algebraic curve in $\RR^2$ (the two curves may or may not be identical). We already know that there could be $O(n)$ distinct distances when the points are on parallel or orthogonal lines. In this more general scenario there exists a third exceptional case --- the case of two concentric circles. We denote by $D_{\text{\em curves}}(n)$ the minimum number of distinct distances between two sets of $n$ points, each on a constant degree algebraic curve, such that the two curves do not contain orthogonal lines, parallel lines, or concentric circles (this also implies that the two curves do not contain common lines or circles). Pach and de Zeeuw \cite{PZ13} extended the technique of \cite{SS13} to obtain $D_{\text{curves}}(n) = \Omega(n^{4/3})$. More generally, they derived the bound $\Omega(\min\{n^{2/3}m^{2/3},m^2,n^2\})$ for the asymmetric case when one curve contains $n$ points and the other $m$ points.

\begin{problem} \label{pr:curves}
Find the asymptotic value of $D_{\text{\em curves}}(n)$.
\end{problem}

In Section \ref{sec:HighD} we consider similar problems in higher dimensions.

\section{Higher dimensions} \label{sec:HighD}

In this section we consider higher-dimensional variants of the distinct distances problem.
Denote by $D_d(n)$ the minimum number of distinct distances that a set of $n$ points in $\RR^d$ can determine. Similarly to the planar case, the current best configuration for the $d$-dimensional case is an $n^{1/d} \times n^{1/d} \times \cdots \times n^{1/d}$ integer lattice. Every distance in this configuration is the square root of a sum of $d$ squares, each with a value between 0 and $n^{2/d}$. Therefore, the number of distinct distances that are determined by such a lattice is $O(n^{2/d})$, implying $D_d(n) = O(n^{2/d})$. This bound was already observed by Erd\H os in his 1946 paper \cite{erd46}, and is conjectured to be tight (for $d\ge 3$).

Solymosi and Vu \cite{SV08} derived the following recursive relations on $D_d(n)$.

\begin{theorem} \label{th:SV} {\bf (Solymosi and Vu \cite{SV08})}
(i) If $D_{d_0}(n) = \Omega(n^{\alpha_0})$, then for all $d>d_0$, we have
\[D_d(n) = \Omega\left( n^{\frac{2d}{(d+d_0+1)(d-d_0)+2d_0/\alpha_0}} \right). \]

(ii) If $D_{d_0}(n) = \Omega(n^{\alpha_0})$, then for all $d>d_0$ where $d-d_0$ is even, we have
\[D_d(n) = \Omega\left( n^{\frac{2(d+1)}{(d+d_0+2)(d-d_0)+2(d_0+1)/\alpha_0}} \right). \]
\end{theorem}

Recall that $D_2(n) = \Omega(n/\log{n})$. Combining this with Theorem \ref{th:SV}(i) implies $D_3(n) = \Omega^*(n^{3/5})$,\footnote{In the $\Omega^*(\cdot)$ notation we neglect polylogarithmic factors; although the logarithm in the denominator of the lower bound for $D_{2}(n)$ does not exactly fit the formulation of Theorem \ref{th:SV}, the proof remains valid.} while the above lattice example implies $D_3(n) = O(n^{2/3})$. These are the current best bounds for $D_3(n)$.
The current best bounds for larger values of $d$ are obtained by combining Theorem \ref{th:SV}(ii) with the bounds $D_2(n)=\Omega^*(n)$ and $D_3(n)=\Omega^*(n^{3/5})$ as base cases. That is, for even $d\ge4$ we have $D_d(n) = \Omega^*\left(n^{\frac{2d+2}{d^2+2d-2}}\right)$ and for odd $d\ge5$ we have $D_d(n) = \Omega^*\left(n^{\frac{2d+2}{d^2+2d-5/3}}\right)$.
Notice that as $d$ goes to infinity $D_d(n)$ approaches the conjectured bound $\Theta(n^{2/d})$.

\begin{problem} \label{pr:Rd}
Find the asymptotic value of $D_d(n)$.
\end{problem}

It seems possible that the techniques that were used by Guth and Katz \cite{GK15} for analyzing $D(n)$ could also be applied to the higher dimensional variant. However, so far it is still not clear how to extend some of the steps in this analysis.

Let $D_d^{o}(n)$ denote the minimum number of distinct distances that a set of $n$ points on a hypersphere in $\RR^d$ can determine. Tao \cite{Tao11} observed that the bound from \cite{GK15} remains valid when the point set is on a sphere in $\RR^3$ (or on a hyperbolic plane). That is, $D_3^{o}(n) = \Omega(n/\log{n})$. For a lower bound, place a set of $n$ points on a circle that is on the sphere, so that they form the vertices of a regular planar $n$-gon (recall figure \ref{fi:sec2}(b)). This implies $D_3^{o}(n) = O(n)$.

\begin{problem} \label{pr:sphere}
Find the asymptotic value of $D_3^o(n)$.
\end{problem}

Erd\H os, Fu\"redi, Pach, and Ruzsa \cite{EFPR93} proved $D_4^o(n) = O(n/\log \log n)$ and $D_d^o(n) = O(n^{2/(d-2)})$ for $d>4$.
These bounds are obtained by taking an integer lattice in $\RR^d$ and then choosing a sphere that contains many lattice points. No lower bound is known beyond the trivial $D_d^o(n) \ge D_d(n)$.

\begin{problem} \label{pr:sphereD}
Find the asymptotic value of $D_d^o(n)$ for $d\ge4$.
\end{problem}

\paragraph{Restricted point sets.}
Charalambides \cite{Chara13} considered the case where a set of $n$ points is contained in a constant-degree curve $C$ in $\RR^d$ (i.e., the $d$-dimensional variant of Problem \ref{pr:curves}).
He showed that if $C$ contains an \emph{algebraic helix} (see \cite{Chara13} for a description of this family of curves. In $\RR^2$ and $\RR^3$ the only algebraic helices are lines and circles) the points may determine only $O(n)$ distinct distances. On the other hand, if $C$ does not contain any algebraic helices,
the points on it determine $\Omega(n^{5/4})$ distinct distances. We denote by $D_{\text{\em curve}}^{(d)}(n)$ the minimum number of distinct distances that are determined by $n$ points on a $d$-dimensional
curve which does not contain an algebraic helix.

\begin{problem} \label{pr:curveD}
Find the asymptotic value of $D_{\text{\em curve}}^{(d)}(n)$.
\end{problem}

 In the rather special case of curves that have a polynomial parametrization, Raz, Sharir, and Solymosi \cite{RSS14} improve Charalambides' bound to $\Omega(n^{4/3})$. In this case, the only restriction on the curve is that it must not contain any lines (i.e., no other type of algebraic helix has such a parametrization).

It also seems natural to ask what happens when the point sets are restricted to surfaces. That is, the minimum number of distances between a set $\pts_1$ of $n$ points on a surface $S_1$ and a set $\pts_2$ of $n$ points on a surface $S_2$, both in $\RR^d$.
For example, consider the case where $S_1$ and $S_2$ are non-parallel planes in $\RR^3$. Then there are two orthogonal lines $\ell_1,\ell_2$ such that $\ell_1 \subset S_1$, $\ell_2 \subset S_2$, and $\ell_1 \cap \ell_2$ is a point on $S_1 \cap S_2$. By placing two sets of points on $\ell_1,\ell_2$ as depicted in Figure \ref{fi:TwoLines}, we obtain $\Theta(n)$ distinct distances. The same bound can be obtained between two spheres and between a sphere and a plane.
However, even these special cases are far from being settled, since an unrestricted set of $n$ points in $\RR^3$ can determine only $\Theta(n^{2/3})$ distinct distances.
No non-trivial bound is known for surfaces in $\RR^3$.

\begin{problem} \label{pr:surfs}
Consider two sets of points in $\RR^3$, each contained in a surface. For which surfaces can the number of distinct distances between the two sets be sublinear? For which surfaces this number must be superlinear?
\end{problem}

\section{Subsets with no repeated distances} \label{sec:subset}

This section surveys problems that concern point subsets that determine every distance at most once. Table \ref{ta:subset} lists the current best bounds for the problems that are presented in this section.

\begin{table}[h]
\begin{center}
\caption{Current best bounds for the problems of Section \ref{sec:subset}. \label{ta:subset}}
\vspace{2mm}

\begin{tabular}{|c|c|c|}
\hline
{\textbf {Variant}} & {\textbf {Lower bound}} & {\textbf {Upper bound}} \\
\hline\hline
$\s(n)$  & $\Omega(n^{1/3}/\log^{1/3} n)$ \cite{Chara12,GK15,LT95} & $O\left(\sqrt{n}/(\log n)^{1/4}\right)$ \cite{EG70} \\ \hline
\ignore{$\s_O(n)$  & $\Omega(n^{1/3}/\log^{1/3} n)$ \cite{Chara12,Tao11} & $O\left(\sqrt{n}\right)$ (trivial) \\ \hline}
$\s(\lattice)$  & $\Omega(n^{1/3}/\log^{1/3} n)$ \cite{EG70} & $O\left(\sqrt{n}/(\log n)^{1/4}\right)$ \cite{EG70} \\ \hline
$\s(\lattice_d)$  & $\Omega(n^{2/(3d)})$ \cite{LT95} & $O(n^{1/d})$ (trivial) \\ \hline
$\s_d(n)$ & $\Omega\left(n^{1/(3d-3)}(\log n)^{1/3 -2/(3d-3)}\right)$ \cite{CFGHUZ14} & $O(n^{1/d})$ (trivial) \\ \hline
$\s'(n)$  & $\Omega(n^{0.4315})$ & $O\left(\sqrt{n}/(\log n)^{1/4}\right)$ \cite{EG70} \\ \hline

\end{tabular}
\end{center}
\vspace{-\baselineskip}
\end{table}

\begin{figure}[h]

\centerline{\placefig{gridSubset}{0.5\textwidth}}
\vspace{-1mm}

\caption{\small \sf A set of 25 points and a subset of four points that span every distance at most once. No subset of five points has this property.}
\label{fi:gridSubset}
\vspace{-2mm}
\end{figure}

Given a set $\pts$ of points in $\RR^2$, let $\s(\pts)$ denote the size of the largest subset $\pts' \subset \pts$ such that every distance is spanned by the points of $\pts'$ at most once; that is, there are no points $a,b,c,d \in \pts'$ such that $|ab|=|cd|>0$ (including cases where $a=c$).
Figure \ref{fi:gridSubset} depicts a set of 25 points and a subset of four points that span every distance at most once.
Let $\s(n) = \min_{|\pts|=n}\s(\pts)$. In other words, $\s(n)$ is the maximum number satisfying the property that every set of $n$ points in the plane contains a subset of $\s(n)$ points that do not span any distance more than once.
Erd\H os \cite{Erd57,EG70,EP95} posed the following problem.

\begin{problem} \label{pr:subset} {\bf (Erd\H os)}
Find the asymptotic value of $\s(n)$.
\end{problem}

Let $\pts$ be a point set that spans $d$ distinct distances. Notice that if all of the distances that are spanned by the points of a subset $\pts' \subset \pts$ are unique, then the number of distances that are spanned by $\pts$ must be at least $\binom{|P'|}{2}$, or equivalently $|\pts'|=O\left(\sqrt{d}\right)$.
Let $\lattice$ be a $\sqrt{n}\times \sqrt{n}$ integer lattice. Recall that Erd\H os \cite{erd46} showed that the number of distinct distances that are spanned by $\lattice$ is $\Theta(n/\sqrt{\log n})$ (e.g., see Section \ref{sec:structure} of this document). Therefore, we have $\s(n) \le \s(\lattice) = O\left(\sqrt{n}/(\log n)^{1/4}\right)$.
Lefmann and Thiele \cite{LT95} derived the bound $\s(n)=\Omega(n^{0.25})$ by using a probabilistic argument. Dumitrescu \cite{Dum08} improved this bound to $\s(n)=\Omega(n^{0.288})$ by combining it with an upper bound of Pach and Tardos \cite{PT02} on the maximum number of isosceles triangles that can be spanned by a set of $n$ points. Recently, Charalambides \cite{Chara12} combined the probabilistic argument of Lefmann and Thiele with a result from Guth and Katz's distinct distances paper \cite{GK15}, to obtain the following improved result and simple proof.

\begin{theorem} \label{th:subset} {\bf (Charalambides \cite{Chara12})}
$\s(n)=\Omega(n^{1/3}/\log^{1/3} n)$.
\end{theorem}
\begin{theProof}{\!\!}
Consider a set $\pts$ of $n$ points in $\RR^2$. Similarly to the Elekes-Sharir reduction, we define the set
\[ Q_1 = \left\{ (a,b,c,d)\in \pts^4 \ \big| \ |ab|=|cd|>0 \right\}, \]

such that every quadruple of $Q_1$ consists of four distinct points. Guth and Katz \cite{GK15} proved that $|Q_1|=O(n^3\log n)$ (also for the case where $Q_1$ is allowed to contain quadruples where not all four points are distinct). Let $Q_2$ be the set of isosceles and equilateral triangles that are spanned by points of $\pts$.

Let $\pts' \subset \pts$ be a subset that is obtained by selecting every point of $\pts$ with a probability $0 < p <1$ that will be determined below.
We have $\EE[|\pts'|] = p n$. Let $Q_1' \subset Q_1$ be the set of quadruples of $Q_1$ that contain only points of $\pts'$. Every quadruple of $Q_1$ is in $Q_1'$ with a probability of $p^4$, so $\EE[|Q_1'|] \le \alpha p^4 n^3\log{n}$, for a sufficiently large constant $\alpha$. Let $Q_2'$ be the set of triangles of $Q_2$ that contain only points of $\pts'$. The bound of Pach and Tardos implies $\EE[|Q_2'|] \le \alpha p^3 n^{2.137}$, for sufficiently large $\alpha$.
Notice that the points of $\pts'$ span every distance at most once if and only if $|Q_1'|=|Q_2'|=0$.
By linearity of expectation, we have
\begin{equation*}
\EE\left[|\pts'|-|Q_1'|-|Q_2'|\right]\ge p n - \alpha p^4 n^3\log{n} - \alpha p^3 n^{2.137}.
\end{equation*}

By setting $p=1/(2\alpha n^2\log n)^{1/3}$, for sufficiently large $n$ we obtain
\begin{equation*}
\EE\left[|\pts'|-|Q_1'|-|Q_2'|\right]> \frac{n^{1/3}}{3(\alpha\log n)^{1/3}}.
\end{equation*}
Therefore, there exists a subset $\pts' \subset \pts$ for which $|\pts'|-|Q_1'|-|Q_2'|\ge \frac{n^{1/3}}{3(\alpha\log n)^{1/3}}$. Let $\pts''$ be a subset of $\pts'$ that is obtained by removing from $\pts'$ a point from every element of $Q_1'$ and $Q_2'$. The subset $\pts''$ does not span any repeated distances and contains $\Omega(n^{1/3}/\log^{1/3} n)$ points of $\pts$.
\end{theProof}

\ignore{
Let $\s_O(n)$ denote the maximum number satisfying the property that every set of $n$ points on a sphere in $\RR^3$ contains a subset of $\s_O(n)$ points that do not span any distance more than once. Charalambides \cite{Chara12} showed that a simple extension of the proof of Theorem \ref{th:subset} implies $\s(n)=\Omega(n^{1/3}/\log^{1/3} n)$. This requires an extension of Guth and Katz's distinct distances result to points on a sphere, as derived by Tao \cite{Tao11}. Let $\pts_r$ be the set of vertices of a regular $n$-gon in $\RR^3$. It can be easily verified that the points of $\pts_r$ determine $O(n)$ distinct distances and are contained in a common sphere. This implies $\s_O(n)=O(\sqrt{n})$.

\begin{problem}
Find the asymptotic value of $\s_O(n)$.
\end{problem} }

Erd\H os and Guy \cite{EG70} considered the following special case of Problem \ref{pr:subset}.

\begin{problem} \label{pr:Lat}{\bf (Erd\H os and Guy \cite{EG70})}
Find the asymptotic value of $\s(\lattice)$, where $\lattice$ is a $\sqrt{n}\times \sqrt{n}$ integer lattice.
\end{problem}

As mentioned above, the current best upper bound for $\s(\lattice)$ is $O\left(\sqrt{n}/(\log n)^{1/4}\right)$. Erd\H os and Guy \cite{EG70} derived the bound $\s(\lattice) = \Omega(n^{1/3-\varepsilon})$, which was later improved by Lefmann and Thiele \cite{LT95} to $\s(\lattice) = \Omega(n^{1/3})$. This bound is still marginally better than the bound implied by Theorem \ref{th:subset}.

Erd\H os and Guy \cite{EG70} also considered the higher dimensional variant of Problem \ref{pr:Lat}. That is, they considered a $d$-dimensional lattice $\lattice_d$ of the form $n^{1/d}\times \cdots \times n^{1/d}$. Similarly to the planar case, Erd\H os and Guy \cite{EG70} derived the bound $\s(\lattice_d) = \Omega(n^{2/(3d)-\varepsilon})$, and this was later improved by Lefmann and Thiele \cite{LT95} to $\s(\lattice_d) = \Omega(n^{2/(3d)})$.
It is simple to show that the points of $\lattice_d$ span $O(n^{2/d})$ distinct distances (e.g., see Section \ref{sec:HighD} of this document), which implies $\s(\lattice_d) = O(n^{1/d})$.

\begin{problem}{\bf (Erd\H os and Guy \cite{EG70})}
Find the asymptotic value of $\s(\lattice_d)$, where $\lattice_d$ is an $n^{1/d}\times \cdots \times n^{1/d}$ integer lattice.
\end{problem}

We can also consider the higher dimensional variant of Problem \ref{pr:subset}. Let $\s_d(n)$ denote the maximum number satisfying the property that every set of $n$ points in $\RR^d$ contains a subset of $\s_d(n)$ points that do not span any distance more than once.
Thiele \cite[Theorem 4.33]{Thiele95} proved the lower bound $\s_d(n)=\Omega(n^{1/(3d-2)})$.
Recently, this was improved by Conlon, Fox, Gasarch, Harris, Ulrich, and Zbarsky \cite{CFGHUZ14} to $\s_d(n)=\Omega\left(n^{1/(3d-3)}(\log n)^{1/3 -2/(3d-3)}\right)$.
The current best upper bound is $\s_d(n)\le \s(\lattice_d) = O(n^{1/d})$.

\begin{problem}
Find the asymptotic value of $\s_d(n)$ for $d\ge 3$.
\end{problem}

In the open problems book of Brass, Moser, and Pach \cite{BMP05}, they offer a problem of a similar flavor. Let $\s'(n)$ denote the maximum number satisfying the property that every set of $n$ points in the plane contains a subset of $\s'(n)$ points that do not span any isosceles triangles.

\begin{problem} {\bf (Brass, Moser, and Pach \cite{BMP05})}
Find the asymptotic value of $\s'(n)$.
\end{problem}

For a trivial upper bound, we have $\s'(n) \le s(n) = O\left(\sqrt{n}/(\log n)^{1/4}\right)$. By adapting the proof of Theorem \ref{th:subset} (i.e., removing $Q_1$ from the analysis), we obtain $s'(n) = \Omega(n^{0.4315})$.

\section{Every $k$ points determine at least $l$ distinct distances.}\label{sec:kl}

Let $\phi(n,k,l)$ denote the minimum number of distinct distances that are determined by a planar $n$ point set $\pts$ with the property that any $k$ points of $\pts$ determine at least $l$ distinct distances (this notation is taken from \cite[Chapter 5]{BMP05}). That is, by having a local property of every small subset of points, we wish to obtain a global property of the entire point set. Table \ref{ta:secKL} lists the current best bounds for most of the problems that are discussed in this section.

\begin{table}[h]
\begin{center}
\caption{The current best bounds for some of the problems that are presented in Section \ref{sec:kl}.\label{ta:secKL}}
\vspace{2mm}

\begin{tabular}{|c|c|c|}
\hline
{\textbf {Variant}} & {\textbf {Lower bound}} & {\textbf {Upper bound}} \\
\hline\hline
$\phi(n,3,2)$  & $\Omega(n/\log n)$ \cite{GK15} & $O(n/\sqrt{\log n})$ \cite{erd46} \\ \hline
$\phi(n,3,3)$  & $\Omega(n)$ & $n2^{O(\sqrt{\log n})}$ \cite{erd86} \\ \hline
$\phi(n,4,3)$  & $\Omega(n/\log n)$ \cite{GK15} & $O(n/\sqrt{\log n})$ \\ \hline
$\phi(n,4,4)$  & $\Omega(n/\log n)$ \cite{GK15} & $n2^{O(\sqrt{\log n})}$ \cite{Dum08} \\ \hline
$\phi(n,4,5)$  & $\Omega(n)$ (trivial) & $O(n^2)$ (trivial) \\ \hline
$\phi(n,5,9)$  & $\Omega(n)$ (trivial) & $O(n^2)$ (trivial) \\ \hline
\end{tabular}
\end{center}
\vspace{-\baselineskip}
\end{table}

\noindent {\bf The case $\mathbf{\emph{k=3}}$.} The value of $\phi(n,3,2)$ is the minimum number of distinct distances that are determined by a set of $n$ points that do not span any equilateral triangles. As discussed in Section \ref{sec:structure}, Erd\H os \cite{erd46} noticed that a $\sqrt{n}\times\sqrt{n}$ integer lattice determines $\Theta(n/\sqrt{\log n})$ distinct distances. It is known that the points of the integer lattice do not determine any equilateral triangles, and thus $\phi(n,3,2)= O(n/\sqrt{\log n})$. Guth and Katz's bound on $D(n)$ \cite{GK15} implies $\phi(n,3,2)= \Omega(n/\log n)$. Thus, the current best bounds for $\phi(n,3,2)$ are identical to the ones for $D(n)$.

\begin{problem} \label{pr:n32}
Find the asymptotic value of $\phi(n,3,2)$.
\end{problem}

The value of $\phi(n,3,3)$ is the minimum number of distinct distances that are determined by a set of $n$ points that do not span any isosceles triangles (here and in the following cases, we also consider degenerate polygons, such as a degenerate isosceles triangle whose three vertices are collinear). Since no isosceles triangles are allowed, every point determines $n-1$ distinct distances with the other points of the set, and thus we have $\phi(n,3,3) = \Omega(n)$.
Erd\H os \cite{erd86} observed the following upper bound for $\phi(n,3,3)$.
Behrend \cite{Behr46} proved that there exists a set $A$ of positive integers $a_1<a_2<\cdots<a_n$, such that no three elements of $A$ determine an arithmetic progression and that $a_n < n2^{O(\sqrt{\log n})}$.
Therefore, the point set $\pts_1 = \{(a_1,0), (a_2,0),\ldots, (a_n,0)\} \subset \RR^2$ does not span any isosceles triangles. Since $\pts_1 \subset \pts_2 = \{(1,0),(2,0),\ldots,(a_n,0) \}$ and $D(\pts_2)< n2^{O(\sqrt{\log n})}$, we have $\phi(n,3,3) < n2^{O(\sqrt{\log n})}$.
Erd\H os conjectured \cite{erd86} that $\phi(n,3,3) = \omega(n)$.

\begin{problem} \label{pr:n33}
Find the asymptotic value of $\phi(n,3,3)$.
\end{problem}

\noindent {\bf The case $\mathbf{\emph{k=4}}$.} The value of $\phi(n,4,3)$ is the minimum number of distinct distances that are determined by a set of $n$ points that do not span any squares. This case is somewhat similar to the one of $\phi(n,3,2)$. The $\sqrt{n}\times\sqrt{n}$ triangular lattice determines $\Theta(n/\sqrt{\log n})$ distinct distances (e.g., see \cite{Sblog14}). Since the triangular lattice does not contain any squares, we have $\phi(n,4,3) = O(n/\sqrt{\log n})$. The current best lower bound $\phi(n,4,3) = \Omega(n/\log n)$ is Guth and Katz's general bound.

\begin{problem} \label{pr:n43}
Find the asymptotic value of $\phi(n,4,3)$.
\end{problem}

\begin{figure}[h]

\centerline{\placefig{deltoid}{0.6\textwidth}}
\vspace{-1mm}

\caption{\small \sf (a) The point $p$ is equidistant from the other three vertices of the deltoid. (b) The only possible cases of segments having the same length are $|ab|=|cd|$ and $|ac|=|bd|$.}
\label{fi:deltoid}
\vspace{-2mm}
\end{figure}

The value of $\phi(n,4,4)$ is the minimum number of distinct distances that are determined by a set of $n$ points that do not span any rhombuses, rectangles, or deltoids with one vertex that is equidistant to the three other three (see Figure \ref{fi:deltoid}(a)). Dumitrescu \cite{Dum08} observed that $\phi(n,4,4)< n2^{O(\sqrt{\log n})}$ by using the same point set $\pts_1$ from the analysis of $\phi(n,3,3)$. Indeed, consider a subset of four points of $\pts_1$, as depicted in Figure \ref{fi:deltoid}(b), and notice that the only pairs of segments that are allowed to have the same length (without resulting in an arithmetic progression) are $|ab|=|cd|$ and $|ac|=|bd|$. Thus, every quadruple of points determines at least four distinct distances.
No lower bound is known beyond $\phi(n,4,4)=\Omega(n/\log n)$.

\begin{problem} \label{pr:n44}
Find the asymptotic value of $\phi(n,4,4)$.
\end{problem}

Not much is known about the case of $\phi(n,4,5)$. Erd\H os \cite{erd86} asked whether $\phi(n,4,5)=\Theta(n^2)$, though the current best lower bound is only $\phi(n,4,5)= \Omega(n)$.
Indeed, when considering an $n$ point set $\pts$ with this property, we notice that any circle whose center is a point of $\pts$ can be incident to at most two points of $\pts$.

\begin{problem} \label{pr:n45}
Find the asymptotic value of $\phi(n,4,5)$.
\end{problem}

Finally, we have the trivial bound $\phi(n,4,6) = n(n-1)/2$, since every distance can occur at most once in this case.

\noindent {\bf The case $\mathbf{\emph{k=5}}$.} We do not go over the various cases of $k=5$, and only mention that Erd\H os \cite{erd86} asked whether $\phi(n,5,9)=\Omega(n^2)$. Again, nothing is known in this case beyond the trivial $\phi(n,5,9)=\Omega(n)$.

\begin{problem} \label{pr:n59}
Find the asymptotic value of $\phi(n,5,9)$.
\end{problem}

\noindent {\bf The general case.} Erd\H os \cite{erd86} noticed that, for any $k\ge 3$, we have

\[\phi\left(n,k,\binom{k}{2}-k+3\right) = \Omega(n). \]

To see why, consider a set $\pts$ of $n$ points such that every $k$-point subset of $\pts$ determines at least $\binom{k}{2}-k+3$ distinct distances, and a point $p\in\pts$. If $p$ is the center of a circle that is incident to $k-1$ points of $\pts$, then together these $k$ points determine at most $\binom{k}{2}-k+2$ distinct distances, contradicting the assumption on $\pts$. Thus, the points of $\pts\setminus \{p\}$ are contained in at least $(n-1)/(k-2)$ circles around $p$, which in turn implies that $p$ determines $\Omega(n)$ distinct distances with the other points of $\pts$.

Another simple observation is that, for any $k\ge 4$, we have

\[ \phi\left(n,k,\binom{k}{2}-\lfloor k/2 \rfloor +2 \right) = \Omega(n^2), \]

since in this case every distance can occur at most $\lfloor k/2 \rfloor -1$ times.

Similarly to the cases of $\phi(n,3,3)$ and $\phi(n,4,4)$, we can use the set $\pts_1$ to obtain a bound of $n2^{O(\sqrt{\log n})}$ for various $\phi(n,k,l)$. For example, it is not hard to show that
\[\phi\left(n,k,2\lfloor k/2 \rfloor\right)=n2^{O(\sqrt{\log n})}. \]

It seems likely that a more careful analysis would yield the same bound for larger values of $l$.

\begin{problem} \label{pr:nkl}
Find stronger general bounds for $\phi(n,k,l)$.
\end{problem}

\section{Additional problems} \label{sec:additional}
In this section we discuss problems that did not fit into any of the previous sections.

In Problems \ref{pr:lines}, \ref{pr:curves}, and \ref{pr:surfs}, we considered bipartite distinct distances problems, where we have two sets of points $\pts_1$ and $\pts_2$, and are interested only in distinct distances that are spanned by pairs of $\pts_1\times\pts_2$ (i.e., distances between points from different sets). We now consider a somewhat different bipartite problem, where  $\pts_1$ is a set of three points and $\pts_2$ is a set of $n$ points, both in $\RR^2$. A simple argument shows that the number of distinct distances between two such sets is $\Omega(n^{1/2})$. Elekes \cite{Elek95} constructed a configuration where the three points of $\pts_1$ are evenly spaced on a line, and the number of distinct distances between the two sets is $\Theta(n^{1/2})$, thus settling this problem.

We denote by $D(3,n)$ the minimum number of distinct distances between a set $\pts_1$ of three \emph{non-collinear} points and a set $\pts_2$ of $n$ points.
Elekes and Szab\'o \cite{ES12} proved the bound $D(3,n)=\Omega(n^{0.502})$, showing that collinearity is necessary for obtaining a bound of $\Theta(n^{1/2})$. Recently, Sharir and Solymosi \cite{SSo13} obtained a more significant improvement, proving $D(3,n)=\Omega(n^{6/11})$. The current best upper bound is the trivial $D(3,n)= (n/\sqrt{\log n})$.

\begin{problem}
Find the asymptotic value of $D(3,n)$.
\end{problem}

Another bipartite variant was recently suggested by Sharir, Smorodinsky, Valculescu, and de Zeeuw \cite{SSmo14}.
Denote by $L(m,n)$ the minimum number of distinct distances between a set of $m$ points and a set of $n$ \emph{lines}, both in $\RR^2$ (where the distance between a point and a line is defined in the usual way).
By placing $m$ points on a line $\ell$ and then taking $n$ lines that are parallel to $\ell$, we obtain  $L(m,n) = O(n)$. When $\sqrt{m}< n <m^2$, the bound $L(m,n) = \Omega( m^{1/5} n^{3/5} )$ was derived in \cite{SSmo14}.

\begin{problem}
Find the asymptotic value of $L(m,n)$.
\end{problem}

We next consider a variant of Problem \ref{pr:mainPnt}. Given a planar point set $\pts$ and a point $p \in\pts$, we denote by $\hd_p(\pts)$ the number of distinct distances between $p$ and the other points of $\pts$. We set $\hd_\Sigma(\pts)=\sum_{p\in\pts}\hd_p(\pts)$ and $\hd_\Sigma(n) = \min_{|\pts|=n}\hd_\Sigma(\pts)$. It is not hard to verify that if $\pts$ is a $\sqrt{n}\times\sqrt{n}$ integer lattice, then $\hd_\Sigma(\pts) = \Theta\left(n^2/\sqrt{\log n}\right)$. Erd\H os conjectured \cite{Erd75,erd87} that this should also be the value of $\hd_\Sigma(n)$.

\begin{problem}
Find the asymptotic value of $\hd_\Sigma(n)$.
\end{problem}

The current best lower bound $\hd_\Sigma(n) = \Omega(n^{1.864})$ is immediately implied by Katz and Tardos' \cite{KT04} bound $\hd(n) = \Omega(n^{(48-14e)/(55-16e)})\approx \Omega(n^{0.864})$ (by repeatedly removing a point $p$ that maximizes $\hd_p(\pts)$).

Next, we consider a generalization from distinct distances to \emph{distinct vectors}. Given a planar point set $\pts$, we denote by $v(\pts)$ the number of distinct vectors that are spanned by pairs of points of $\pts$ (i.e., the points $p,q$ span the vectors $p-q$ and $q-p$), and set $v(n) = \min_{|\pts|=n}v(\pts)$. Clearly, $v(n)$ should be at least as large as $D(n)$. In fact, it is also not hard to show that $v(n) = \Theta(n)$. Indeed, the $\sqrt{n}\times\sqrt{n}$ integer lattice determines $\Theta(n)$ distinct vectors.

Erd\H os, F\"uredi, Pach, and Ruzsa \cite{EFPR93} studied the case of distinct vectors for point sets in general position (i.e., no three points on a line and no four points on a circle). We set $v_\text{gen}(n) = \min_{|\pts|=n}v(\pts)$, where the sum is taken over every set of $n$ points in general position. In \cite{EFPR93}, it is proven that $v_\text{gen}(n) > cn$ for \emph{every} constant $c$; i.e., $v_\text{gen}(n) =\omega(n)$. The current best upper bound  $v_\text{gen}(n) = n2^{O(\log n)}$ is immediately implied by the current best upper bound for Problem \ref{pr:gen}.

\begin{problem}
Find the asymptotic value of $v_\text{gen}(n)$.
\end{problem}

\vspace{3mm}

\noindent {\bf Acknowledgements.} The author is indebted to the various people who helped improve this survey. These are Adrian Dumitrescu, William Gasarch, Ben Lund, Micha Sharir, and Frank de Zeeuw.

config: arxiv


TITLE: Determining if function odd or even
QUESTION [2 upvotes]: This exercise on the Khan Academy requires you to determine whether the following function is odd or even
f(x) = $-5x^5 - 2x - 2x^3$
To answer the question, the instructor goes through the following process

what is f(-x)
f(-x) = $-5(-x)^5 - 2(-x) - 2(-x)^3$
f(-x) = $5(x)^5 +2(x) + 2(x)^3$
f(-x) = $-(-5x^5 - 2x - 2x^3)$
f(-x) = -f(x)

Therefore f(x) is odd.
Question. Why is everything converted to a negative both inside and outside the parenthesis at step 4?
At step 2, he's making x negative. At step 3, we get the result of making the x values negative. So why add the negatives again at step 4?

REPLY [0 votes]: In step 4, the instructor is factoring out a $-1$.
Just like $2a + 4b + 6c$ can be factored into $2(a + 2b + 3c)$, so can $5x^5 +2x + 2x^3$ be factored into $-1(-5x^5 - 2x - 2x^3)$.  He just omitted the $1$ when writing it.
The reason he factored out a $-1$ is because that makes the inner expression the same as $f(x)$, and he's attempting to prove that $f(-x) = -f(x)$.


TITLE: Peano Addition is recursive?
QUESTION [0 upvotes]: Looking at this Wikipedia article on Peano's Axioms, specifically on addition, I see $(2)$ saying that
$a + S(b) = S(a + b)$
It is called recursive, but I'm not clear why, in and of itself, this is necessarily recursive -- other than by immediately jumping into the example where adding successive numbers to $a$ are built up from $(2)$ starting from $(1)$ where $a + 0 = a$.
But if you don't start "at the beginning," this would imply $a + b = a + S(k)$ where $b = S(k)$ -- which might imply $k = b - 1$, so
$a + b = a + b - 1 = S(a + b - 1) = a + b - 1 + 1$
assuming $S(a + b - 1) = a + b - 1 + 1$ ... which seems circular and pointless. It seems like I've jumped to the conclusion that $1$ (either adding or subtracting) is what addition within the context of succession is based on. Can, must I do this? Seen in a programming language, you decrement $b$, then add the decremented $b$ to $a$, then increment the sum. What have I gained for this exercise? Yes, building up from $0$ "inductively" is interesting, however, starting with any old $a + b$ seems to stretch things badly. Taken with this quote (above in the article):

Axioms 1, 6, 7, 8 define a unary representation of the intuitive
  notion of natural numbers: the number 1 can be defined as S(0), 2 as
  S(S(0)), etc. However, considering the notion of natural numbers as
  can be derived from the axioms, axioms 1, 6, 7, 8 do not imply that
  the successor function generates all the natural numbers different
  than 0. Put differently, they do not guarantee that every natural
  number other than zero must succeed some other natural number.

I'm duly confused. This is something that has always disturbed me about Peano, i.e., that we can't really assume adding $1$ to something is synonymous with its successor, and, likewise subtracting $1$ gets you from $S(a)$ "back to" $a$. "Next" on a integer line sequence is $a + 1$ doesn't really seem supported by the actual definition of successor.

REPLY [2 votes]: The presentation of Peano's Axioms at Wikipedia is unusual. More commonly used these days is that presented at Wolfram Math World. In the notation of set theory, they are:

$0\in N$
$S: N\to N$
$S$ is injective
For all $x\in N$, we have $S(x)\ne 0$
For all $P\subset N$, if $0\in P$ and for all $x\in P$ we also have $S(x)\in P$, then $P=N$

Notice that there is no mention of addition. Using only these axioms, the rules of logic and set theory, we can actually prove the existence of a binary function $+$ on $N$ such that:

For all $x\in N$, we have $x+0=x$
For all $x,y\in N$, we have $x+S(y)=S(x+y)$

This function perfectly models the addition operation that we have all known since childhood. From these two rules, we can determine the sum of any two natural numbers.
Example
To prove $2+3=5$, we start by applying (1) for $x=2$ to obtain:
$2+0=2$.
Then we apply (2) three times to obtain:
$2+1=2+S(0)=S(2+0)= S(2)=3$
$2+2= 2+S(1) = S(2+1)=S(3)=4$
$2+3= 2+S(2) = S(2+2)=S(4)=5$


TITLE: If $X_1$ and $X_2$ are uniformly distributed random variables with parameters $0$ and $1$, what is the distribution of $Y = X_1 + X_2$?
QUESTION [1 upvotes]: I was doing a recap of the probability theory I had last year and even though this question shouldn't be hard, it is somehow confusing me immensly.
Clearly, if we have $X_1, X_2$ belonging to $U[0, 1]$, then $Y = X_1 + X_2$ must have a support of $Y$ belonging to $[0, 2]$, as both $X_1$ and $X_2$ belong to $[0,1]$. By definition, the pdf of $U[0, 1]$ is simply $1$. Now, if I try to find the cdf of $Y$, I find that:
$F_Y(y) = \int_0^y\int_0^{y-x2}f(x_1, x_2)dx_1dx_2 = \int_0^y\int_0^{y-x2}1dx_1dx_2 = \int_0^y(y-x_2)dx_2 = y^2/2$.
For a distribution function, if $y$ tends to its limit, then $F_Y(y)$ tends to $1$. However, if I let $y = 2$, then $F_Y(y) = 2$ as well, which can't be.
I must be doing something incredibly stupidly wrong. Please tell me what it is.

REPLY [1 votes]: You've got (in your outer integral) $x_2$ going from $0$ up to $y$, which can't be right, as $x_2$ never gets bigger than $1$.
You haven't mentioned whether or not $X_1$ and $X_2$ are independent, but if that is the case then you should be able to break the integral down to two cases,
case 1) $0 < y < 1$
case 2) $1 < y < 2$
and be more careful about the limits of integration you use. Remember, $f(x_1, x_2) = 0$ outside of $[0,1] \times[0,1]$.
(If you can't assume that $X_1$ and $X_2$ are independent then you probably won't be able to get any nice closed-form expression for $F_Y$.)


TITLE: Bound on $\sum_{k = 2}^n (en)^k k^{-Cn/\log{n} - k - 1/2}$
QUESTION [3 upvotes]: As the title suggests, I'm trying to establish a good bound on
\begin{equation}
  S(n) = \sum_{k = 2}^n (en)^k k^{-Cn/\log{n} - k - 1/2},
\end{equation}
where $C$ is some reasonably large positive constant. In particular I would like to have $S(n) = o(1)$, i.e.,
\begin{equation}
  \lim_{n \to \infty} S(n) = 0,
\end{equation}
which numerical evaluations suggest to be the case.
Moreover it appears to be the case that the terms in the series are monotonically decreasing; if this were true my claim follows trivially (replace all terms by the one at $k = 2$ and check) but verifying the ''monotone decrease conjecture'' is again a difficult task in itself.
I appreciate any ideas on how to tackle this problem.
EDIT: The sequence terms are unfortunately not monotonically decreasing as can be verified by studying the logarithm of the latter but the conjecture about the term at $k = 2$ being largest still stands.

REPLY [1 votes]: In spite of my previous comment, I do think your intuition is correct.
Attempted proof (sorry but it is very ugly): Again, let $r(d)=\frac{s_2}{s_{2+d}}$. As you noted,
$$
r(d)=\left(\frac{2+d}{en}\right)^d\left(1+\frac{d}{2}\right)^{Cn/\log n + 2 + 1/2}
$$
Taking logarithm, we get
$$
\log r(d)=d\left(\log\left(\frac{2+d}{en}\right)\right)+ (Cn/\log n+2+1/2)\left(\log\left(\frac{2+d}{2}\right)\right)
$$
where $d\in [0,n-2]$. Now, let $\lambda=\frac{2+d}{n}\in[2/n,1]$, or, equivalently, $d=\lambda n - 2$. Thus,
$$
\log r(d)=(\lambda n - 2)\left(\log\left(\frac{\lambda}{e}\right)\right) + (Cn/\log n+2+1/2)\left(\log\left(\frac{\lambda n}{2}\right)\right):=f(\lambda)
$$
Cleaning this mess a bit, we get
$$
f(\lambda)=(\lambda n -2)(\log\lambda - 1) + (Cn/\log n+2+1/2)(\log\lambda + \log n -\log2)\\
= \lambda n(\log\lambda - 1) -2\log\lambda+2+(Cn/\log n + 2 + 1/2)\log\lambda\\
+ Cn + 2.5\log n-2.5\log 2\\
=n(\lambda \log\lambda - \lambda) + (Cn/\log n + 0.5)\log\lambda + D(n)
$$
where $D(n)$ depends only on $n$.
Taking derivative, we get $f'(\lambda)=n\log\lambda + \frac{1}{\lambda}(Cn/\log n + 0.5)$, and the second derivative is $f''(\lambda)=\frac{n}{\lambda} - \frac{1}{\lambda^2}(Cn/\log n + 0.5)=\frac{n}{\lambda^2}(\lambda-C/\log n + 0.5/n)$
Hence. If $n$ is large enough, $f''(\lambda)>0$ for all $\lambda \ge 2/n$. Ie, $f'$ is increasing. Now, for such $n$,
$$
f'\left(\frac{2}{n}\right)=n\log 2 - n\log n + \frac{n}{2}(Cn/\log n + 0.5)\\
=n\log 2 - n\log n + \frac{Cn^2}{2\log n} + n$$
which is bigger than $0$ for large enough $n$. And since $f'$ increasing, $f'>0$ in $[2/n,1]$. Ie, $f$ is increasing. Ie, for large enough $n$, $f(\lambda)\ge 0$ for $\lambda \ge 2/n$. Hence $r(d)\ge 1$ for $d\in [0,n-2]$. Hence $S(n)=o(1)$.