Fdtxjr

Unable to disable Microsoft Store in domain environment

Language involving irrational number is not a CFL

Determining multivariate least squares with constraint

What happens if I try to grapple mirror image?

Is there a RAID 0 Equivalent for RAM?

Are inadvertent environmental catastrophes also examples of natural selection?

Can I cause damage to electrical appliances by unplugging them when they are turned on?

Do you waste sorcery points if you try to apply metamagic to a spell from a scroll but fail to cast it?

Has the laser at Magurele, Romania reached a tenth of the Sun's power?

If Captain Marvel (MCU) were to have a child with a human male, would the child be human or Kree?

Should I assume I have passed probation?

The Digit Triangles

Why would five hundred and five be same as one?

Deciphering cause of death?

How can I, as DM, avoid the Conga Line of Death occurring when implementing some form of flanking rule?

Would a primitive species be able to learn English from reading books alone?

Anime with legendary swords made from talismans and a man who could change them with a shattered body

Why do Radio Buttons not fill the entire outer circle?

If the only attacker is removed from combat, is a creature still counted as having attacked this turn?

Why can't the Brexit deadlock in the UK parliament be solved with a plurality vote?

Why does the Persian emissary display a string of crowned skulls?

What is the meaning of "You've never met a graph you didn't like?"

What is this high flying aircraft over Pennsylvania?

Giving feedback to someone without sounding prejudiced

Minimum number of distinct distances in a plane

Lower bound for a set of distances between pairs of points in a planePairs of points exactly $1$ unit apart in the planeEmbedding finite (discrete) metric spaces to Eulidean space as isometrically as possibleNumber of possible combinations of the Enigma machine plugboardChoosing k pairs l distance apart from n numbersNearly-unit-distance graph (UDG) densityCombinatoral Geometry with DistancesMinimum number of points to intersect any circle in the regionFinding the number of distinct extrema of polynomial.Set of Integers, find expectation of twin pairs (defined in description)

0

$begingroup$

Let $U(n)$ denote the maximum possible number of pairs of points in an $n$-point subset of $Bbb R^2$ that are unit distance apart.

Let $g(n)$ be the minimum number of distinct distances determined by $n$ points in $Bbb R^2$, that is:
$$g(n)=textmin_Pleft|textdist(x,y)mid x,yin Pright|.$$

My textbook says "Clearly $g(n)geq nchoose 2 / U(n)$". Why is this so? I have no idea how to even show that this is reasonable. My first thought is that there are clearly $nchoose 2$ pairs and if $U(n)=nchoose 2$, i.e. they are all unit distance apart, then indeed $g(n)=1$. Otherwise as $U(n)$ gets smaller, $g(n)$ should get bigger, which seems okay intuitively. But I don't see how to show this

Actually, a thought after typing this out: Perhaps they are thinking about taking all pairs, and breaking them up into $U(n)$ sized groups, of which would would have $nchoose 2/U(n)$, and one cannot do better than this.

combinatorics discrete-geometry

share|cite|improve this question

edited Mar 14 at 5:44

Martin Sleziak

44.9k10121274

asked Apr 2 '18 at 15:42

user547222user547222

155

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  How does $U(n)$ depend on $n$?
  $endgroup$
  – Fimpellizieri
  Apr 2 '18 at 15:45
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Fimpellizieri fixed
  $endgroup$
  – user547222
  Apr 2 '18 at 15:46
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes, your afterthought is correct. Obviously there are at most $U(n)$ pairs of points that are any given distance apart, by scaling. So there can't be more that $U(n)$ points in any group, so at most $binomn2/U(n)$ groups.
  $endgroup$
  – saulspatz
  Apr 2 '18 at 15:51
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  This is pigeon-hole, and in fact I'd even say: Clearly, $g(n)ge 1+nchoose 2/U(n)$ for $nge 2$
  $endgroup$
  – Hagen von Eitzen
  Apr 2 '18 at 15:53
  
  

  
  
  
  

add a comment | 

0

$begingroup$

Let $U(n)$ denote the maximum possible number of pairs of points in an $n$-point subset of $Bbb R^2$ that are unit distance apart.

Let $g(n)$ be the minimum number of distinct distances determined by $n$ points in $Bbb R^2$, that is:
$$g(n)=textmin_Pleft|textdist(x,y)mid x,yin Pright|.$$

My textbook says "Clearly $g(n)geq nchoose 2 / U(n)$". Why is this so? I have no idea how to even show that this is reasonable. My first thought is that there are clearly $nchoose 2$ pairs and if $U(n)=nchoose 2$, i.e. they are all unit distance apart, then indeed $g(n)=1$. Otherwise as $U(n)$ gets smaller, $g(n)$ should get bigger, which seems okay intuitively. But I don't see how to show this

Actually, a thought after typing this out: Perhaps they are thinking about taking all pairs, and breaking them up into $U(n)$ sized groups, of which would would have $nchoose 2/U(n)$, and one cannot do better than this.

combinatorics discrete-geometry

share|cite|improve this question

edited Mar 14 at 5:44

Martin Sleziak

44.9k10121274

asked Apr 2 '18 at 15:42

user547222user547222

155

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  How does $U(n)$ depend on $n$?
  $endgroup$
  – Fimpellizieri
  Apr 2 '18 at 15:45
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Fimpellizieri fixed
  $endgroup$
  – user547222
  Apr 2 '18 at 15:46
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes, your afterthought is correct. Obviously there are at most $U(n)$ pairs of points that are any given distance apart, by scaling. So there can't be more that $U(n)$ points in any group, so at most $binomn2/U(n)$ groups.
  $endgroup$
  – saulspatz
  Apr 2 '18 at 15:51
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  This is pigeon-hole, and in fact I'd even say: Clearly, $g(n)ge 1+nchoose 2/U(n)$ for $nge 2$
  $endgroup$
  – Hagen von Eitzen
  Apr 2 '18 at 15:53
  
  

  
  
  
  

add a comment | 

$begingroup$

Let $U(n)$ denote the maximum possible number of pairs of points in an $n$-point subset of $Bbb R^2$ that are unit distance apart.

Let $g(n)$ be the minimum number of distinct distances determined by $n$ points in $Bbb R^2$, that is:
$$g(n)=textmin_Pleft|textdist(x,y)mid x,yin Pright|.$$

My textbook says "Clearly $g(n)geq nchoose 2 / U(n)$". Why is this so? I have no idea how to even show that this is reasonable. My first thought is that there are clearly $nchoose 2$ pairs and if $U(n)=nchoose 2$, i.e. they are all unit distance apart, then indeed $g(n)=1$. Otherwise as $U(n)$ gets smaller, $g(n)$ should get bigger, which seems okay intuitively. But I don't see how to show this

Actually, a thought after typing this out: Perhaps they are thinking about taking all pairs, and breaking them up into $U(n)$ sized groups, of which would would have $nchoose 2/U(n)$, and one cannot do better than this.

combinatorics discrete-geometry

share|cite|improve this question

edited Mar 14 at 5:44

Martin Sleziak

44.9k10121274

asked Apr 2 '18 at 15:42

user547222user547222

155

$endgroup$

share|cite|improve this question

edited Mar 14 at 5:44

Martin Sleziak

44.9k10121274

asked Apr 2 '18 at 15:42

user547222user547222

155

share|cite|improve this question

edited Mar 14 at 5:44

Martin Sleziak

44.9k10121274

asked Apr 2 '18 at 15:42

user547222user547222

155

edited Mar 14 at 5:44

Martin Sleziak

44.9k10121274

edited Mar 14 at 5:44

Martin Sleziak

44.9k10121274

asked Apr 2 '18 at 15:42

user547222user547222

155

asked Apr 2 '18 at 15:42

user547222user547222

155

1 Answer
1

active

oldest

votes

0

$begingroup$

Given an $n$-set $Ssubset mathbb R^2$, consider

$$mathscr S = (x,y),.$$

Obviously, $|mathscr S| = binomn2$.
Now, define an equivalence relationship $sim$ on $mathscr S$ by

$$ (x_0,y_0) sim (x_1,y_1) iff d(x_0,y_0) = d(x_1,y_1).$$

The relation $sim$ partitions $mathscr S$ into some number $k$ of classes, each of which has most $U(n)$ elements.
Hence, $k geq leftlceilbinomn2/U(n)rightrceil geq binomn2/U(n)$.

Now, we know there are least $g(n)$ classes.
Suppose that we chose $S$ a priori such that $k = g(n)$.
This is possible, for otherwise $g(n)$ would not be a minimum.

With this choice, the inequality follows.
Notice that the inequality depends on $n$, but not on $S$.
Using our freedom to choose $S$ can make it easier to prove the inequality.

share|cite|improve this answer

edited Apr 2 '18 at 16:10

answered Apr 2 '18 at 15:57

FimpellizieriFimpellizieri

17.2k11836

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Really neat, thanks!
  $endgroup$
  – user547222
  Apr 2 '18 at 16:18
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You're welcome! Glad to help.
  $endgroup$
  – Fimpellizieri
  Apr 2 '18 at 16:19
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2718927%2fminimum-number-of-distinct-distances-in-a-plane%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

0

$begingroup$

Given an $n$-set $Ssubset mathbb R^2$, consider

$$mathscr S = (x,y),.$$

Obviously, $|mathscr S| = binomn2$.
Now, define an equivalence relationship $sim$ on $mathscr S$ by

$$ (x_0,y_0) sim (x_1,y_1) iff d(x_0,y_0) = d(x_1,y_1).$$

The relation $sim$ partitions $mathscr S$ into some number $k$ of classes, each of which has most $U(n)$ elements.
Hence, $k geq leftlceilbinomn2/U(n)rightrceil geq binomn2/U(n)$.

Now, we know there are least $g(n)$ classes.
Suppose that we chose $S$ a priori such that $k = g(n)$.
This is possible, for otherwise $g(n)$ would not be a minimum.

With this choice, the inequality follows.
Notice that the inequality depends on $n$, but not on $S$.
Using our freedom to choose $S$ can make it easier to prove the inequality.

share|cite|improve this answer

edited Apr 2 '18 at 16:10

answered Apr 2 '18 at 15:57

FimpellizieriFimpellizieri

17.2k11836

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Really neat, thanks!
  $endgroup$
  – user547222
  Apr 2 '18 at 16:18
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You're welcome! Glad to help.
  $endgroup$
  – Fimpellizieri
  Apr 2 '18 at 16:19
  

  
  
  
  

add a comment | 

0

$begingroup$

Given an $n$-set $Ssubset mathbb R^2$, consider

$$mathscr S = (x,y),.$$

Obviously, $|mathscr S| = binomn2$.
Now, define an equivalence relationship $sim$ on $mathscr S$ by

$$ (x_0,y_0) sim (x_1,y_1) iff d(x_0,y_0) = d(x_1,y_1).$$

The relation $sim$ partitions $mathscr S$ into some number $k$ of classes, each of which has most $U(n)$ elements.
Hence, $k geq leftlceilbinomn2/U(n)rightrceil geq binomn2/U(n)$.

Now, we know there are least $g(n)$ classes.
Suppose that we chose $S$ a priori such that $k = g(n)$.
This is possible, for otherwise $g(n)$ would not be a minimum.

With this choice, the inequality follows.
Notice that the inequality depends on $n$, but not on $S$.
Using our freedom to choose $S$ can make it easier to prove the inequality.

share|cite|improve this answer

edited Apr 2 '18 at 16:10

answered Apr 2 '18 at 15:57

FimpellizieriFimpellizieri

17.2k11836

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Really neat, thanks!
  $endgroup$
  – user547222
  Apr 2 '18 at 16:18
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You're welcome! Glad to help.
  $endgroup$
  – Fimpellizieri
  Apr 2 '18 at 16:19
  

  
  
  
  

add a comment | 

$begingroup$

Given an $n$-set $Ssubset mathbb R^2$, consider

$$mathscr S = (x,y),.$$

Obviously, $|mathscr S| = binomn2$.
Now, define an equivalence relationship $sim$ on $mathscr S$ by

$$ (x_0,y_0) sim (x_1,y_1) iff d(x_0,y_0) = d(x_1,y_1).$$

The relation $sim$ partitions $mathscr S$ into some number $k$ of classes, each of which has most $U(n)$ elements.
Hence, $k geq leftlceilbinomn2/U(n)rightrceil geq binomn2/U(n)$.

Now, we know there are least $g(n)$ classes.
Suppose that we chose $S$ a priori such that $k = g(n)$.
This is possible, for otherwise $g(n)$ would not be a minimum.

With this choice, the inequality follows.
Notice that the inequality depends on $n$, but not on $S$.
Using our freedom to choose $S$ can make it easier to prove the inequality.

share|cite|improve this answer

edited Apr 2 '18 at 16:10

answered Apr 2 '18 at 15:57

FimpellizieriFimpellizieri

17.2k11836

$endgroup$

share|cite|improve this answer

edited Apr 2 '18 at 16:10

answered Apr 2 '18 at 15:57

FimpellizieriFimpellizieri

17.2k11836

answered Apr 2 '18 at 15:57

FimpellizieriFimpellizieri

17.2k11836

answered Apr 2 '18 at 15:57

FimpellizieriFimpellizieri

17.2k11836