On existence of integral point sets and their diameter bounds
Nikolai Avdeev












	On existence of integral point sets and their diameter bounds
	[
		This work was carried out at Voronezh State University and supported by the Russian Science
		Foundation grant 19-11-00197.
	]

    
	N.N. Avdeev
	[nickkolok@mail.ru, avdeev@math.vsu.ru]

    
====================================================================================================================================================================================================





  
Abstract.
A point set M in m-dimensional Euclidean space is called an integral point set if all the distances between the
elements of M are integers, and M is not situated on an (m-1)-dimensional hyperplane.
We improve the linear lower bound for diameter of planar integral point sets.
This improvement takes into account some results related to the Point Packing in a Square problem.
Then for arbitrary integers m ≥ 2, n ≥ m+1, d ≥ 1
we give a construction of an integral point set M of n points in m-dimensional Euclidean space,
where M contains points M_1 and M_2 such that distance between M_1 and M_2 is exactly d.





§ INTRODUCTION

Let ℕ be the set of all positive integers and let |M_1 M_2| denote the Euclidean distance
between points M_1 and M_2 in a finite-dimensional space ℝ^m
(and, more generally, let |Δ| denote the length of line segment Δ).
An integral point set in m-dimensional Euclidean space is a point set M such that all the distances between the
points of M are integers and M is not situated on an (m-1)-dimensional hyperplane.
Erdös and Anning proved <cit.> that every integral point set consists of a finite number of points.
Taking this into account, we denote the set of all integral point sets of n points in m-dimensional Euclidean space by
𝔐(m,n) (using the notation in <cit.>)
and denote the set of all integral point sets in m-dimensional Euclidean space by 𝔐(m,ℕ).
The symbol # M will be used for cardinality of M, that is the number of points in M in our case.

For every finite point set, its diameter is naturally defined as

    diam M = max_A,B∈ M |AB|
    	.

Another emerging question is: how does the diameter of an integral point set depend on its cardinality?
One can easily see that every M∈𝔐(m,n) with diam M = h
can be dilated to M_p∈𝔐(m,n) with diam M = ph
for every p∈ℕ.
So, the above question should be rephrased:
how does the least possible diameter of an integral point set depend on its cardinality?
In order to answer this question, the following function was introduced <cit.>:

    d(m,n) = min_M∈𝔐(m,n)diam M = min_M∈𝔐(m,n)max_A,B∈ M |AB|
    	.

We also refer to <cit.> for a list of known exact values of d(m,n)
and its bounds; in the present paper, the case of m=2 will mostly be in the focus.

The most significant breakthrough on the planar case was done by Solymosi <cit.>,
who proved that cn ≤ d(2,n) for a sufficiently small constant c.
Following Solymosi's proof carefully,
one can derive that the inequality holds at least for c = 1/24.
(See <cit.> for some remarks.)
The constant was improved in <cit.> to 1/8 for all n and in <cit.>
to 3/8 for sufficiently large n.

The paper <cit.> contains one more interesting result.
Let us define a function which is “dual” to d(m,n) in some sense:

    l(m,n) = min_M∈𝔐(m,n)min_A,B∈ M |AB|
    	.

Solymosi proved that l(2,n)≤ 2.

In the present paper we improve Solymosi's results:
first, we obtain a larger constant c = 5/11 in Theorem <ref>,
using the combined approach with the Point Packing in a Square problem
(this approach is different from Solymosi's one);
second, we prove that l(m,n)=1 for all possible m and n.



§ LOWER BOUND FOR THE DIAMETER


In this section,
we improve the lower bound for minimum diameter of planar integral point sets
employing Point Packing in a Square problem.
Below we introduce the problem, basic notions and results.

[Point Packing in a Square (PPS) <cit.>]
	
	Given an integer k > 1, place k points in the unit square U = [ 0 , 1 ]^2 such that their
	minimum pairwise distance m is maximal.



	For each k > 1, the corresponding maximal distance m from Problem <ref>
	is called the k-th PPS coefficient and denoted by φ_k.

So, it's impossible to place k points in a unit square in such a way that each pairwise distance of the points is greater than φ_k.



	
	<cit.>
	For every k≥ 2 the following inequality holds:
	
    √(2/k√(3))≤φ_k
    		≤1/k-1 +
    		√(1/(k-1)^2
    			+
    			2/(k-1)√(3))




To prove the bound on d(2,n), we also need the following results and notions from <cit.>.


	<cit.>
	
	Let M∈𝔐(2,n), diam M = d.
	Then M is situated in a square of side length d.



	A cross for points M_1 and M_2, denoted by cr(M_1,M_2), is the union of two straight lines:
	the line through M_1 and M_2,
	and the perpendicular bisector of line segment M_1 M_2.



	
	If open line segments M_1 M_2 and M_3 M_4 do not intersect,
	
	then the set cr(M_1,M_2) ∩ cr(M_3,M_4) is either a straight line or contains 2 or 4 points.

It is important that we consider the intersection of open line segments,
so e.g. the cases M_1 = M_3 and M_3 ∈ M_1 M_2 satisfy the conditions of Lemma <ref>.


	
	Let ABCD be a convex quadrilateral on the plane.
	Then max{AC,BD}>min{AB,BC,CD,DA},
	that is at least one diagonal is greater than at least one side.



Basing on the exact values of d(2,n) for 3 ≤ n≤ 122 and the estimate d(2,123)>10000
<cit.>, we derive the following proposition.

	
	The inequality
	
    d(2,n) ≥ 3^1/4·2^-3/2· n

	holds for 4 ≤ n ≤ 21491.


Therefore, we will focus on planar integral points sets of more than 21491 points.

Performing some simple manipulations with the upper bound in Theorem <ref>,
one can derive the following proposition.

	
	For n ≥ 21492 we have
	
    φ_n ≤φ_n-1≤β/√(n-2)
    		,

	where
	
    β = 1/√(21490) + √(2/√(3) + 1/21490) < 1.07464
    		.



Now we need to estimate the cardinality of an intersection of an integral point set with a line segment.
Assuming that the planar integral point sets contains many collinear points,
the following result holds.
 <cit.>
	For δ > 0, ε > 0, and P∈𝔐(2,n) with
	at least n^δ collinear points there exists a n_0 (ε)
	such that for all n ≥ n_0 (ε) we have
	
    diam P ≥ n^δ/4 log 2(1+ε)loglog n
    		.


However, the estimate is rather unsuitable for our needs,
as it does not provide the values of all the constants.
To obtain the needed estimate, we now prove a generalization of <cit.>.


	For a line segment M_1 M_2 and an integer k, such that -|M_1 M_2| < k < |M_1 M_2|,
	we define a ρ(k,M_1 M_2)-curve as the set of points N
	for which the equality |N M_1| - |N M_2| = k holds.

So, in the planar case a ρ(k,M_1 M_2)-curve
is a branch of a hyperbola for k≠ 0 and the perpendicular bisector of line segment M_1 M_2 for k=0.


	
	If points M_1,M_2,M_3,M_4 are situated on a straight line,
	the equality |M_1 M_2| = |M_3 M_4| holds and line segments M_1 M_2 and M_3 M_4 do not coincide,
	then for a fixed k the ρ(k,M_1 M_2)-curve and the ρ(k,M_3 M_4)-curve
	do not intersect.



	
	Let M ∈𝔐(2,ℕ) and let m be a straight line.
	Then for every k∈ℕ there are at most 2k-1 segments Δ_i ⊂ m with endpoints in M,
	such that |Δ_i| = k.


	Consider a point N∈ M ∖ m.
	Then for each Δ_i there is a ρ(n_i,Δ_i)-curve containing N.
	Due to Proposition <ref>, all n_i are distinct;
	otherwise the ρ(n_i,Δ_i)-curve and the ρ(n_i,Δ_j)-curve, j≠ i, do not intersect.
	There can be only 2k-1 distinct values for n_i,
	so there are at most 2k-1 distinct segments Δ_i.



	
	Let Δ be a straight line segment, |Δ|=l and M ∈𝔐(2,ℕ).
	Let #(Δ∩ M) = n^2 + 1.
	Then
	
    l ≥2/3n^3+1/2n^2-1/6n
    		.




	Any n^2+1 points, including the endpoints of Δ, partition the segment Δ into n^2
	sequential segments Δ_i.
	Due to Lemma <ref>, there is at most one segment of length 1,
	at most three segments of length 2, etc.
	The following two expressions for sums conclude the proof:
	
    1 + ∑_k=1^n (2k-1) = n^2 + 1
    		,

	
    ∑_k=1^n k(2k-1) = 2/3n^3+1/2n^2-1/6n
    		.



Now we will estimate the length of a line segment that intersects an integral point set
by an arbitrary number of points.


	Let Δ be a straight line segment, |Δ| = b and M ∈𝔐(2,ℕ).
	Let #(Δ∩ M) = t.
	Then
	
    b≥2/3t^3/2-3/2t+5/6t^1/2
    		.




	Let f(k) denote the mininal length of a line segment
	that intersects an integral point set by k points.
	We observe that f(k) > f (k-1).
	Due to Lemma <ref>,
	f(n^2+1) ≥2/3n^3+1/2n^2-1/6n.

	
	
	For t∈ℕ the inequality (√(t) - 1)^2 +1 ≤ t holds,
	thus
	
	
    f(t) ≥ f((√(t) - 1)^2 +1) ≥2/3(√(t) - 1)^3+1/2(√(t) - 1)^2-1/6(√(t) - 1)
    		=
    		2/3t^3/2-3/2t+5 /6t^1/2
    		.



This lemma leads to the following proposition.


	
	Let Δ be a straight line segment, |Δ| = b and M ∈𝔐(2,ℕ).
	Let #(Δ∩ M) = k and b>10000.
	Then k ≤γ_2 b + 6,
	where
	
    γ_2 = 3846/2593 √(647)-5823 = 0.063958...




	We know the maximum number of points for planar integral point sets of diameters at most 10000.
	Thus, we are interested in integral t such that estimate (<ref>)
	holds for b > 10000.
	So, let us consider t≥ 647 and find a coefficient γ_2,
	such that the inequality
	
    2/3t^3/2-3/2t+5 /6t^1/2≥t-6/γ_2

	holds for all t≥ 647.
	For such t,
	the left-hand side of (<ref>) obviously grows faster than the right-hand side.
	Turning (<ref>) into the same equality
	and solving it for t=647, we obtain the required estimate.


Now we are ready to prove the main theorem of the section.


	
	If n≥ 4, then d(2,n) ≥γ (n - 2),
	where
	
    0.46530... =
    		3^1/4· 2^-3/2 >
    		
     >
    		γ = √(16 ( √(2/√(3)+1/21490)+1/√(21490)) ^2+14791716/( 2593 √(647)-5823) ^2)-3846/2593 √(647)-5823/8 ( √(2/√(3)+1/21490)+1/√(21490)) ^2
    		>
    
    		> 0.45557
    		> 5/11
    		.




	For 4 ≤ n ≤ 21491, the assertion of the theorem follows immediately from Proposition <ref>.
	Let us consider M∈𝔐(2,n), n ≥ 21492, diam M = b.
	Lemma <ref> yields that M is situated in a square of side length b.
	Let M_1, M_2, M_3, M_4 be points of M such that the distances |M_1 M_2| and |M_3 M_4|
	are minimal in M (M_2 and M_3 may coincide).
	Then |M_1 M_2| ≤ bφ_n-1 and |M_3 M_4| ≤ bφ_n-1.
	Due to Lemma <ref>, open line segments M_1 M_2 and M_3 M_4 do not intersect
	(otherwise they are not minimal).

	Let C = cr(M_1 M_2) ∩ cr(M_3 M_4).
	Each point N∈ M satisfies one of the following conditions:

	a) N belongs to C — overall at most γ_2 b + 6 points by Lemma <ref> and Proposition <ref>;

	b) N belongs to the intersection of one of |M_1 M_2| - 1 hyperbolas
	with one of |M_3 M_4| - 1 hyperbolas — overall at most 4 (|M_1 M_2| - 1)(|M_3 M_4| - 1) points;

	c) N belongs to the intersection of one of |M_1 M_2| - 1 hyperbolas with cr(M_3 M_4) —
	overall at most 4 (|M_1 M_2| - 1) points;

	d) N belongs to the intersection of one of |M_3 M_4| - 1 hyperbolas with cr(M_1 M_2) —
	overall at most 4 (|M_3 M_4| - 1) points;

	(see <cit.> for details).
	Summing up the above cases, we obtain the following estimate:
	
    n ≤ 4 b^2 φ_n-1^2 - 4 + γ_2 b + 6
    		.

	Proposition <ref> turns estimate (<ref>)
	into the following:
	
    n-2 ≤ 4 b^2 β^2/n-2 + γ_2 b
    		,

	which obviously leads to inequality
	
    1 ≤ 4β^2 (b/n-2)^2  + γ_2 b/n-2
    		.

	Let us denote λ = b/(n-2) and solve the following quadratic inequality for λ:
	
    4β^2 λ^2  + γ_2 λ - 1 ≥ 0
    		.

	The discriminant is γ_2^2 + 16 ·β^2,
	so we obtain the following estimate:
	
    b/n-2 = λ≥-γ_2 + √(γ_2^2 + 16 ·β^2)/8β^2
    		.

	Calculating the expression above for our β and γ_2, we conclude the proof.



	If n≥ 4, then d(2,n) > 5/11 n.



	For 4 ≤ n ≤ 21491, the claim follows from Proposition <ref> immediately.
	For n > 21491, the inequality 0.45557(n-2) > 5/11n holds.



We can improve the constant in Theorem <ref>,
if some new exact values of d(2,n) are found;
however, the obtained constant is bounded by 3^1/4·2^-3/2 above.
More precisely, we have the following theorem.


	For every ε > 0 there exists a number n_0 such that the inequality
	
    d(2,n) ≥ n·(3^1/4· 2^-3/2 - ε)

	holds for every n>n_0,
	that is
	
    lim_n→∞d(2,n)/n≥ 3^1/4· 2^-3/2
    		.







§ CONSTRUCTING INTEGRAL POINT SETS



	A set M∈𝔐(2,n) is called facher
	if M consists of n-1 points on a straight line
	and one point out of the line.



	A set M∈𝔐(m,n) is called optimal
	if diamM=d(m,n).



	<cit.>
	A squarefree number q is called the characteristic of M∈𝔐(2,ℕ),
	if for any points M_1, M_2, M_3 ∈ M the area of triangle M_1 M_2 M_3
	is p_1,2,3√(q) for some rational p_1,2,3.

For a given M∈𝔐(2,ℕ), the characteristic is determined uniquely.

Facher sets are the simplest planar integral point sets.
It is known that for 9≤ n ≤ 122 all the optimal sets are facher <cit.>.
For every cardinality n and every squarefree number q
there exists a facher set M∈𝔐(2,n) with characteristic q <cit.>.
In <cit.>, the facher sets of characteristic 1 were investigated; they were called semi-crabs.

For every integer n≥ 3 Solymosi presented <cit.> a construction of a facher integral point set
M∈𝔐(2,n)
such that equality |M_1 M_2| = 2 holds for some M_1, M_2 ∈ M.
The constructed set has both odd and even distances.

Now we improve Solymosi's result.


	
	Let us choose a positive integer k > 1 and set
	
    a = 2^2^k - 1
    		.

	Then
	
    a ≡ 3  4

	and, moreover,
	
    a = (2^2^k-1)^2 - 1
    		=
    		(2^2^k-1 + 1) (2^2^k-1 - 1)
    		=
    		
    =
    		(2^2^k-1 + 1) (2^2^k-2 + 1) · ... ·(2^2^1 + 1) (2^2 - 1)
    		.

	We set d_j = 2^2^j + 1 for 1 ≤ j ≤ k-1.
	Then d_j ≡ 1  4.

	Let c_J = ∏_j∈ J d_j for every subset of indices J⊂ I = {1,2,...,k-1}
	(and  c_∅ = 1).
	We obtain
	
    c_J≡ 1 4

	and, moreover, a is divisible by c_J.


	Statements (<ref>) and (<ref>) yield a/c_J ≡ 3  4.
	Let b_J = (c_J - a/c_J)/2, then b_J ≡ 1  2.
	Let us further take g_J = (c_J + a/c_J)/2, then g_J ≡ 0  2.

	Next we define the coordinates of the points as following:
	
    M_J± =(±b_J/2, 0)
    		,
    		  
    		N   =(0, √(a)/2)
    		.

	Then the distances are:
	
    |N M_J±|
    		=
    		(b_J^2/4 + a/4)^1/2
    		=
    		1/2((c_J - a/c_J/2)^2 + a)^1/2
    		=
    		
    =
    		1/2( (c_J/2)^2 - a/2 + (a/c_j)^2 + a)^1/2
    		=
    		1/2( (c_J/2)^2 + a/2 + (a/c_j)^2    )^1/2
    		=
    		
    =
    		1/2((c_J + a/c_J/2)^2)^1/2
    		=
    		1/2(c_J + a/c_J/2)
    		=
    		g_J/2∈ℕ
    		,

	
    |M_J_1 ±  M_J_2 ±|
    		=
    		|b_J_1/2±b_J_2/2|
    		=
    		|b_J_1± b_J_2/2|
    		∈ℕ
    		.

	In particular, for H = {k-1} we obtain C_H = 2^2^k-1+1 and
	
    b_H =
    		( 2^2^k-1+1 - a/2^2^k-1+1)/2
    		=
    		(2^2^k-1+1 - (  2^2^k-1-1 ) )/2
    		=
    		1
    		.

	Thus, one of the distances is
	
    |M_H+  M_H-|
    		=
    		|b_H/2 - -b_H/2|
    		=
    		|1/2 - -1/2|
    		= 1
    		.


	Note that all the points M_J± are distinct:
	the equality b_J =  b_K implies J=K;
	the equality b_J = -b_K implies c_J = -c_K or c_J = a / c_K.
	The first case is impossible because both c_J and c_K are positive;
	the second case contradicts (<ref>) and (<ref>).


	So, M = { M_J±, N} is indeed a planar integral point set of 2^k+1 points,
	and distance 1 occurs in M.
	Since k can be taken arbitrary large, it follows that we can construct
	a planar integral point set of arbitrary large cardinality so that the distance 1 occurs in that set.



	
	Applying Construction <ref> to k=1 naively,
	we get a = 3, I=∅, b_∅ = -1 and then
	obtain an equilateral triangle of side length 1.
	This triangle is obviously the optimal set in 𝔐(2,3).



	
	For k=2 in Construction <ref>,
	we obtain the optimal set in 𝔐(2,5) presented in <cit.>.
	If we remove one point from it,
	then we get one of the two optimal sets in 𝔐(2,4).






	<cit.>
	A set M∈𝔐(m,n) is maximal,
	if there is no set M'∈𝔐(m,n+1)
	such that M ⊊ M'.










Setting k=1 in Lemma <ref>,
we obtain the following result (which is exactly <cit.>).

	
	Let M ∈𝔐(2,ℕ) and let m be a straight line.
	Then there is at most one pair of points M_1,M_2∈ M ∩ m
	such that |M_1 M_2| = 1.


In order to describe all the sets M ∈𝔐(2,n) with distance 1,
we need <cit.>.
For the reader's convenience, we will state a slightly rephrased version of it and provide the proof.

	
	Let M={M_1,M_2,M_3,M_4}∈𝔐(2,4) such that |M_1 M_2|=1.
	If l is the straight line through points M_1 and M_2,
	then one of the points M_3 or M_4 belongs to l.



	Let m denote the perpendicular bisector of line segment M_1 M_2.
	Due to the triangle inequality, there are two possibilities to place each of points M_i, i=3,4:

	a) M_i belongs to l and |M_i M_1|-|M_i M_2| = ± 1;

	b) M_i belongs to m and |M_i M_1| = |M_i M_2|.

	If (a) is true for both points, then M⊂ l and thus M is not an integral point set.
	If (a) is true for one point and (b) is true for another, then the claim of the lemma follows.
	So, suppose to the contrary, that both points M_3 and M_4 belong to m.

	The area of the triangle M_1 M_3 M_4 is rational because |M_3 - M_4| ∈ℤ.
	Thus, the characteristic of M is 1,
	and there is a Cartesian coordinate system such that M_1=(-1/2,0), M_2=(1/2,0), M_3=(0, a/2)
	(see <cit.>).
	It is clear that a≠ 0.
	We set b = |M_1 - M_3| and O=(0,0).
	Applying the Pythagorean theorem to triangle OM_1M_3, we obtain the following Diophantine equation:
	
    1/4 + a^2/4 = b^2
    		,

	or, equivalently,
	
    1 + a^2 = (2b)^2
    		.

	This equation has no integral solutions.
	This contradiction concludes the proof.


Using Construction <ref>,
Lemma <ref> and Corollary <ref>
together with results of <cit.>,
we obtain the following theorem.


	
	For every n≥ 3 there is a planar integral set M of n points
	such that for some M_1,M_2 ∈ M equality |M_1 M_2|=1 holds.
	This set consists of n-1 points, including M_1 and M_2, on a straight line and one point out of the line.

	And vice versa, if M is a planar integral point set of n points
	such that for some M_1,M_2 ∈ M equality |M_1 M_2|=1 holds,
	then M consists of n-1 points, including M_1 and M_2, on a straight line,
	and one point out of the line, on the perpendicular bisector of line segment M_1 M_2.
	There is only one maximal integral point set M' ⊇ M,
	and the perpendicular bisector is the axis of symmetry for M'.
	Moreover, if n > 3, then the distance 1 occurs in M (and M') only once.


Using the “blowing up” procedure described in <cit.>,
we can construct an integral point set M in m-dimensional Euclidean space, m≥ 3,
with distance 1 occuring in it.
If we have an integral point set with distance 1 occuring,
then we can easily dilate it to turn 1 into the desired distance.
These facts, together with Theorem <ref>, give the following theorem.


	For arbitrary integers m ≥ 2, n ≥ m+1, d ≥ 1
	there exists M∈𝔐(m,n),
	such that for some M_1, M_2∈ M equality |M_1 M_2| = d holds.




	<cit.>
	We will call an integral point set M prime, if the greatest common divisor
	of all the distances occuring in M is 1.


If an integral point set is prime,
then it cannot be squashed to an integral point set of the same power and structure but smaller diameter.



	
	For every m ≥ 3, n ≥ m+1, d ≥ 1 there exists a prime
	integral point set M∈𝔐(m,n) which
	contains points M_1 and M_2 such that distance between M_1 and M_2 is exactly d.



	Take a facher integral point set according to Construction <ref>
	with sufficiently large height and then apply the “blowing up” procedure described in <cit.>,
	replacing the out-of-line point with an (m-2)-dimensional simplex of proper side length.
	That simplex will consist of m-1 points;
	we can throw out up to all points M_J, except the two points with distance 1.
	So, the set consists of m+1 or more points and has distance 1 occuring in it.
	As distance 1 occurs in the obtained set, it is prime.


A slightly stronger result can also be claimed.


	
	For arbitrary integers m > 2, n ≥ m+1, d ≥ 1
	there exists a prime set M∈𝔐(m,n),
	such that for some M_1, M_2∈ M equality |M_1 M_2| = d holds,
	the distance d is minimal and occurs in M only once.



	We apply Construction <ref> to obtain M'∈𝔐(2,n-m+2)
	with M'_1, M'_2 ∈ M' and |M'_1 M'_2| = 1.
	Dilate M' to M” in such a way that M'_1 and M'_2 turn into M”_1 and M”_2 resp.
	and |M”_1 M”_2| = d.
	Then “blow up” M” to M∈𝔐(m,n) using a simplex of side length d+1.
	The greatest common divisor of d and d+1 is 1, so M is prime.





§ FINAL REMARKS AND OPEN PROBLEMS



	The bound of Theorem <ref> is not tight.
	The derivation of tight bounds for the minimum diameter d(2, n)
	is still a challenging task for the forthcoming investigation <cit.>.

The known upper bound is d(2,n)≤ 2^c log n loglog n <cit.>.
However, we hope that the present article can provide a framework for possible better estimates.


	The approach of Theorem <ref> can be generalized to higher dimensions.

For the overview of current lower bounds for higher dimensions, we refer the reader to <cit.>.

There are also several ways to improve the current bound,
based on Lemma <ref>.


	
	Is there a number δ < 1 such that any M∈𝔐(2,ℕ) with diam M = d
	is situated in a square of side length d^δ?

If the answer for Problem <ref> is affirmative,
then we can obtain a bound better than linear.


	
	What are the maximal numbers δ≤ 1 and h ≤ 0
	such that any M∈𝔐(2,ℕ) with diam M = d
	is situated in a square of side length δ d - h?


If the answer for Problem <ref> is not δ = 1 and h = 0,
then the linear bound can be slightly improved.

However, Problems <ref> and <ref>
do not seem to show the way for improving the bound
due to the following well-known theorem,
which can be proved by an application of inversion <cit.>.

	
	There exists a dense subset P of the unit circle such that for any P_1, P_2 ∈ P
	the distance |P_1 P_2| is rational.

We conjecture that thorough investigation of existing examples of circular integral point sets
 <cit.>
will lead to the negative answers for the
Problems <ref> and <ref>.

Another possibility to increase the constant in our lower bound is introduced by the following problem.


	
	What is the minimal shape 𝒮 such that any M∈𝔐(2,ℕ) with diam M = d
	is situated in  𝒮?

This problem is another generalization of Lemma <ref>.
We know that 𝒮 is not a circle of diameter d
(the counterexample is an equilateral triangle of side length d)
and we conjecture that 𝒮 is not a Reuleaux triangle of width d
(the possible counterexample belongs to a circle of diameter d, see Theorem <ref>).

The solution to Problem <ref> (if ever found) will lead to a sophisticated packing problem,
something like “How to put n points in a convex hull of concentric circle and Reuleaux triangle?”
Obviously, Problem <ref> can be generalized to higher dimensions.


For n=3,4,5, there are optimal sets in 𝔐(2,n) that contain distance 1
(see Remarks <ref> and <ref>).
However, we can suggest the following conjecture.

	
	Every set M∈𝔐(2,n), n≥ 6, such that for some M_1,M_2 equality |M_1 M_2|=1 holds,
	is not optimal.


The motivation for Conjecture <ref> is based on the results of <cit.>,
especially the following theorem.


	For every 12 ≤ n ≤ 122, there exist a facher optimal sets M_n∈𝔐(2,n)
	that consist of n-1 points { (b_1,0), ..., (b_n-1,0)}
	and the point (0,√(A_n)),
	where b_1,...,b_n-1, A_n are integer and √(A_n)∉ℕ.

Such a set can not contain distance 1: due to Theorem <ref>,
the points with distance 1 should be (± 1/2, 0).

For planar integral point sets containing distance 1, we can emphasise on the following problem.

	For given n≥ 3 and squarefree number q ≠ 1,
	is there M∈𝔐(2,n), such that characteristic of M is q
	and distance 1 occurs in M?


The consideration of integral point sets containing distance 1 in higher dimensions gives a rise to another problem.


	How many times can the distance 1 occur in a set M∈𝔐(m,n)?

The answer for m=2 is given by Theorem <ref>.
For greater m, we will be bold enough to suggest the following conjecture.

	Consider M∈𝔐(m,n), M_1,M_2∈ M, |M_1 M_2| =1.
	Then either n = m+1 or M is a “blowup” of a facher set and distance 1 occurs in M
	no more than 1+(m-1)^2 - (m-1)/2 times.

Such estimate is based on the number of edges in an (m-2)-dimensional simplex.

We want to conclude the list of conjectures with the one which appears the easiest to deal with.



	
	For every n ≥ 3, d ≥ 1 there exists an prime
	set M∈𝔐(2,n) which
	contains points M_1 and M_2 such that distance between M_1 and M_2 is exactly d.

This conjecture gives the same claim as Theorem <ref> does, but for m=2.
Obviously, Theorem <ref> can be generalized (for m=2) into a similar conjecture.




§ ACKNOWLEDGEMENTS

Author thanks Dr. Prof. E.M. Semenov for the fruitful discussion and ideas,
A.S. Chervinskaia for the idea of using the term “facher” and other linguistic advices,
and Dr. A.S. Usachev for proofreading.




