7
$\begingroup$

Given an integer set, if the distances between integers in the set are still in the set, what mathematical term should be used to describe that nature? Or what nature does the set have?

For example, $x,y \in \{1,2,3,4\}$, $m=|x-y|$, $m$ still $\in \{1,2,3,4\}$. Is there a discontinuous integer set that has the nature?

$\endgroup$
5
  • $\begingroup$ You also have sets like $\{2,4,6\}$. $\endgroup$
    – Wojowu
    Commented Jul 17, 2022 at 14:41
  • $\begingroup$ Is there any common characteristics to describe these sets? Or how to generate these sets? $\endgroup$
    – hui cj
    Commented Jul 17, 2022 at 14:59
  • $\begingroup$ Are your sets finite or infinite? Do they consist of positive integers only? $\endgroup$
    – Seva
    Commented Jul 17, 2022 at 15:35
  • $\begingroup$ It's hard to figure out what the question is. Is it about metric spaces with integral distances? is it about subsets of the set of integers? and, last but not least, the question "if there is a discontinuous integet set that has the nature" is senseless. $\endgroup$
    – YCor
    Commented Jul 17, 2022 at 15:58
  • $\begingroup$ For the example, $m = 0$ is not in the set. Can x equal y? $\endgroup$
    – spyr03
    Commented Jul 18, 2022 at 14:51

2 Answers 2

15
$\begingroup$

To simplify notation define $\delta(x,y) = |x-y|$. Here's an easier proof (using only Euclid) of the result in the answer that Seva posted: a finite set of positive integers closed under $\delta$ a homogeneous arithmetic progression $\{d, 2d, \ldots, nd\}$.

Let $d = \gcd(A)$. By Euclid's algorithm, $\gcd(x,y)$ can be obtained from $x,y$ by repeated application of $\delta$, so $A$ is closed under pairwise $\gcd$; hence by induction $d \in A$. Then $\max(A) = nd$ for some integer $n$, and $A \subseteq \{d, 2d, \ldots, nd\}$. By repeated application of $\delta(\cdot,d)$ we find that $A$ also contains $(n-1)d$, $(n-2)d$, $(n-3)d$ etc., so $A \supseteq \{d, 2d, \ldots, nd\}$. Therefore $A = \{d, 2d, \ldots, nd\}$, QED.

It soon follows that if $A$ is an infinite set of positive integers and $A$ is closed under $\delta$ then $A$ consists of all positive multiples of $\gcd(A)$.

$\endgroup$
0
11
$\begingroup$

Assuming that your sets are finite and consist of positive integers only, every such set is a homogeneous arithmetic progression $\{d,2d,\dotsc,nd\}$, where $n=|A|$.

For the proof, let $A-A$ be the set of all differences $a_1-a_2$ with $a_1,a_2\in A$, and denote by $D_+$ the set of all positive elements of $A-A$. We have $D_+\subsetneq A$ (the inclusion is strict since the largest element of $A$ is not in $D_+$) and $|D_+|=(|A-A|-1)/2$. It follows that $|A-A|=2|D_+|+1\le 2|A|-1$, which is known to be possible if $A$ is an arithmetic progression only. It is then easy to see that the progression must be of the indicated form $\{d,2d,\dotsc,nd\}$.

Addressing a question in the comments. To derive from $|A-A|=2|A|-1$ that $A$ is an arithmetic progression, one can use induction. Write $A=\{a_1,\dotsc,a_n\}$ with $a_1<\dotsb<a_n$, and let $A_0:=A\setminus\{a_n\}$. We have $(A_0-A_0)\cup\{a_n-a_1,a_1-a_n\}\subseteq A-A$, with the union in the left-hand side disjoint. Consequently, $|A_0-A_0|\le|A-A|-2\le 2|A_0|-1$, and by the induction hypothesis, $A_0$ is an arithmetic progression. Moreover, if $a_n$ were not the next term of this progression, then $(A-A)\setminus (A_0-A_0)$ would additionally contain the elements $\pm(a_n-a_2)$, leading to $|A-A|\ge|A_0-A_0|+4>2|A|-1$, a contradiction.


Here is yet another proof; as far as simplicity is concerned (see Noam's answer), this one is difficult to beat.

Suppose that $A=\{a_1,\dotsc,a_n\}$ has the property in question, where $a_1<\dotsb <a_n$. Since $a_2-a_1$ is an element of $A$ smaller than $a_2$, we must have $a_2-a_1=a_1$; that is, $a_2=2a_1$. Similarly, $a_3-a_1$ is an element of $A$ exceeding $a_2-a_1=a_1$, but smaller than $a_3$; hence, $a_3-a_1=a_2$, implying $a_3=3a_1$. Continuing this way, we get $a_k=ka_1$ for each $k=1,2,\dotsc,n$.

$\endgroup$
7
  • $\begingroup$ Thanks, that is exactly what I want to know! $\endgroup$
    – hui cj
    Commented Jul 17, 2022 at 16:15
  • $\begingroup$ Sorry, I can not figure out the what note | | means in your proof, and why the last equation means only arithmetic progression could be the answer? $\endgroup$
    – hui cj
    Commented Jul 17, 2022 at 16:59
  • $\begingroup$ @huicj: $|S|$ is the number of elements of the set $S$. I updated the answer to address your second question. $\endgroup$
    – Seva
    Commented Jul 17, 2022 at 19:15
  • $\begingroup$ The second one is clear to comprehend. I know what "Moreover, if A0 is a progression (the induction hypotheses), while A is not, then (A−A)∖(A0−A0) additionally contains the elements ±(an−a2)." means, but I still confused about how to deduce A is an arithmetic progression. Maybe I think we should demonstrate $⊆$ in $(A0−A0)∪{an−a1,a1−an}⊆A−A$ is equivalent to $=$? Can you expand a little about this? Thanks again! $\endgroup$
    – hui cj
    Commented Jul 18, 2022 at 7:23
  • $\begingroup$ @huicj: I tried to explain that part of the (first) proof, hope is clear now. $\endgroup$
    – Seva
    Commented Jul 18, 2022 at 7:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .