5
$\begingroup$

Given a set of positive integers consider the graph whose vertices are those integers, two of which are joined by an edge if and only if they have a common divisor greater than 1 (i.e, they are not relatively prime). What is the least (and most) number of edges such a graph of a set of n consecutive integers can have?

Related question: Graphs determined by sets of consecutive integers

$\endgroup$
  • 1
    $\begingroup$ Do you have any examples showing that the number of edges is not necessarily maximized / minimized when the smallest of the $n$ integers is $0$ / $1$? $\endgroup$ – Seva Feb 26 at 15:22
  • $\begingroup$ I have an example. I will refer to it in my post. Gerhard "Relates To A Recent Question" Paseman, 2019.02.26. $\endgroup$ – Gerhard Paseman Feb 26 at 17:07
  • $\begingroup$ I have posted a related problem elsewhere:puzzling.stackexchange.com/questions/80128/… $\endgroup$ – Bernardo Recamán Santos Mar 2 at 0:57
3
$\begingroup$

This does not quite answer the question (and in fact I doubt a satisfactory answer can be given at all, see below), but hopefully sheds some light on the problem.

Let the consecutive integers under consideration be $a+1,\dotsc,a+n$. I prefer to think in terms of the number of pairs $(a+i,a+j)$ with $1\le i\ne j\le n$ such that $\gcd(a+i,a+j)=1$; denoting this number by $\sigma_n(a)$, the number of edges of the graph in question is $\frac12\,(n(n-1)-\sigma_n(a))$.

Since $\gcd(a+i,a+j)=\gcd(a+i,j-i)$, the quantity $\sigma_n(a)$ is periodic in $a$ with the period at most $\mathrm{lcm}(1,2,\dotsc,n-1)$. This allows one to compute the largest and the smallest possible values of $\sigma_n(a)$ in a finite number of steps, for any given $n$. Computations show that for $n=2,\dotsc,10$, the smallest possible values of $\sigma_n(a)$ are $$ 2,4,8,12,20,24,34,42,56, $$ while the largest possible values are $$ 2,6,10,18,22,34,42,56,64. $$

None of these sequences is in the OEIS. I suspect that no explicit, closed-form expression can be given, but it is not difficult to find an expression that allows one to easily compute $\sigma_n(a)$ and establish its asymptotic behavior. Specifically, in view of $\gcd(a+i,a+j)=\gcd(a+i,j-i)<n$ for any $i,j\in[1,n]$ with $i\ne j$, and using the fact that the number of integers in the interval $[a+1,a+n]$ divisible by $d$ is $$ N_d(a,n) = \left\lfloor \frac{a+n}{d} \right\rfloor - \left\lfloor \frac{a}{d} \right\rfloor, $$ we get \begin{align*} \sigma_n(a) &= \sum_{1\le i\ne j\le n} \sum_{d\mid\gcd(a+i,a+j)} \mu(d) \\ &= \sum_{d=1}^{n} \mu(d)\cdot N_d(a,n)(N_d(a,n)-1) \\ &= \sum_{d=1}^{n} \mu(d)\cdot\left( \left\lfloor \frac{a+n}{d} \right\rfloor - \left\lfloor \frac{a}{d} \right\rfloor \right) \left( \left\lfloor \frac{a+n}{d} \right\rfloor - \left\lfloor \frac{a}{d} \right\rfloor - 1\right) \\ &= \sum_{d=1}^{n} \mu(d)\cdot\left( \frac{n}{d} + \theta_n(a,d) \right)\left( \frac{n}{d} + \theta_n(a,d) -1\right), \end{align*} where $|\theta_n(a,d)|\le\frac12$. It follows that $$ \sigma_n(a) = n^2\ \sum_{d=1}^{n} \frac{\mu(d)}{d^2} +O\left(n\sum_{d=1}^n\frac1d+n\right) = \frac6{\pi^2}\,n^2 + O(n\log n) $$ as $n$ grows (uniformly in $a$).

$\endgroup$
  • 1
    $\begingroup$ Since we care only when the gcd is not 1, the period should be a divisor of the primorial of primes less than n. Gerhard "Making Smaller Cycles To Conquer" Paseman, 2019.02.27. $\endgroup$ – Gerhard Paseman Feb 27 at 18:51
  • 1
    $\begingroup$ Also, can't $\sigma_2(a)$ be 2? Gerhard "Mind Your Sigmas And Mus" Paseman. 2019.02.27. $\endgroup$ – Gerhard Paseman Feb 27 at 18:56
  • $\begingroup$ @GerhardPaseman: you are right, my answer needed a small adjustment to properly count pairs $(a+i,a+j)$ with $i=j$; hopefully it is corrected now. $\endgroup$ – Seva Feb 27 at 19:50
  • 1
    $\begingroup$ By the way, one example to keep in mind is (-n/2,n/2) (or translate by n primorial). This is not necessarily optimal but its graph often has more edges than (0,n+1). Gerhard "Think Sieving And Admissible Sets" Paseman, 2019.02.27. $\endgroup$ – Gerhard Paseman Feb 27 at 20:23
  • $\begingroup$ Regarding suspicions, I agree you deserve better. I assert (at the time of this writing) there is an error in your last display, and that 6/pi^2 needs fixing. I also assert it is the kind of error I would make. This is more in the spirit of cooperation than of the spirit of harsh criticism. And, I still like your post. However, I still reserve the right to suspect. Gerhard "Is Hoping That This Helps" Paseman, 2019.02.28. $\endgroup$ – Gerhard Paseman Feb 28 at 17:47
3
$\begingroup$

I am doing this post in parts. For those wanting more while they wait I direct you to 319906.

Let's start with the multigraph (two vertices having multiple edges) case, and worry about the big cliques in this multigraph first. If $n$ is a multiple of 2, we have $n/2$ even numbers and $n/2$ choose 2 edges between them. If $n$ is not a multiple of 2, replace $n/2$ by floor or ceiling of $n/2$, which ever applies.

We can make a similar statement for larger primes $p \lt n$, but I will write 3 for $p$: the interval has $k$ multiples of $3$ and the graph thus has $k$ choose 2 edges between these multiples, where $k$ is floor or ceiling of $n/3$. Even if we don't know $n$, we know there will be something near $n^2/18$ number of edges, and I could write a more exact expression that is within $ 1 + n/3$ of the correct number of edges.

The point is that there is a $C$ so that for $n$ not too small the multigraph will always have close to $Cn^2$ edges with an uncertainty generously bounded by $n(1+ \log\log n)$. This $C$ actually varies slightly with $n$ but for many practical purposes is well approximated by (1/2) (1/4 + 1/9 + 1/25), so I will write 1/4 for $C$ and talk about its exact value later.

Now the problem above deals with a graph, not a multigraph, and the rough estimate above counts graph edges more than once. In the interval, every set of multiples of an odd prime $p$ has half or almost half of those multiples which are even, and so about a quarter of the edges of that clique of multiples belong to the clique of even numbers already. So the number of multigraph edges overshoots the number of graph edges by a factor of close to (1/4)(1/9 + 1/25 + ...). The point here is that an upper bound for the number of graph edges is given by an estimate of multigraph edges, while a lower bound can be gotten by looking at the edges between multiples of the two or the three smallest primes in the interval, and the two numbers will not be very far apart.

Coming next: Some extreme examples.

Edit 2019.02.27:

Seva has in the meantime provided a post containing figures for a related quantity. While I suspect there are some corrections still to be made in that post, I think the order of growth is correct. I will now talk about the graphs for small $n \gt 1$.

It should be noted that an edge occurs only when two numbers share at least one prime factor less than $n$, and therefore the graph for an interval is identical (up to labelling) to one for the interval shifted by a multiple of the appropriate primorial. (We can use symmetry about 0 to consider only about half of the intervals less than the primorial.) So for small $n$ we can quickly check our work.

We ignore n=1 and note n=2 is the two-point empty graph. For n=3 we may also have a path of length one if the interval has two even numbers otherwise it is the empty graph again. For n=4, we have at least one edge for even numbers, and sometimes may have one additional edge attached to this edge for multiples of 3.

Now we observe some general properties. There may be a dense collection of coprimes (numbers not having prime factors less than n) in this interval. So the graph may have infinite diameter. However, among all vertices with positive degree, they will be an even number or adjacent to an even number, so the largest connected component has diameter at most 3, and all other connected components have diameter 0. It is clear that for each n one can find a graph of diameter 3 (include appropriately placed multiples of primes p and q where both are less than n and larger than n/2), and I suspect for n sufficiently large one can always find such a graph with diameter 2 (or even connected component with diameter 2), but this suspicion smells of Goldbach and de Polignac, so I stay uncommitted on the diameter two issue. (Actually, let the interval have a multiple of the primorial, then the connected component has diameter two.)

We have each graph has a clique of about n/2 vertices, one of about n/3 vertices with about half of those vertices shared by the large clique, and one can extend this to cliques of about n/p vertices for primes larger than p. Here is a nice observation: the multiples of p in an interval form an arithmetic progression where, if one looks at gcd between these members divided by p, one gets a smaller graph that looks like one of the graphs on n/p vertices. Thus one can use smaller bounds to predict how much a p-clique shares with cliques induced by smaller primes.

Turning to n=5, we have one graph which has only one edge, one with two edges (and therefore a path), and graphs which have a triangle and possibly one more edge, giving a range of 1 to four edges in the connected component, and always at least one isolated vertex.

For n=6 we always have a component that contains a triangle plus an edge, and sometimes there is one more edge. This gives three possibilities up to isomorphism, with 4 or 5 edges and Max vertex degree is 3 or 4.

Indeed, when n is a primorial (product of primes up to k), every interval has its graph sharing a common subgraph which are the edges induced by multiples of primes up to k. If n is larger than this primorial, there is still the subgraph on the vertex subset representing (say) the left half of the interval, so many of the edges can be quickly determined.

For n=7 we may have any combination of 3 or 4 even numbers in the interval, 2 or 3 multiples of three, and one or two multiples of five, ranging from a low of 4 edges to a high of 9 edges. If there are 9 edges, the connected component has a diameter of two and one isolated vertex, and the 4 edge and 6 edge examples are also unique.

For n=8 we have a clique with six edges, and in addition to the possibilities for three and for five we have the option of an additional edge for multiples of seven. This gives graphs ranging from 7 edges up to 11 edges.

Up next: better numerics.

End Edit 2019.02.27.

Gerhard "Holds The Post Serialization Rights" Paseman, 2019.02.26.

$\endgroup$
  • 3
    $\begingroup$ "I direct you to 319906." Is that a phone number? $\endgroup$ – Gerry Myerson Feb 26 at 21:39
  • 1
    $\begingroup$ No. It is a post number for MathOverflow. mathoverflow.net/q/319906 . Gerhard "It's Like A MathSciNet Reference" Paseman, 2019.02.26. $\endgroup$ – Gerhard Paseman Feb 26 at 22:58
  • $\begingroup$ Funny, since the OEIS sequence A319906 is "Number of prime numbers of the form k^2 + k + 41 below 10^n", somewhat related. $\endgroup$ – kodlu Feb 26 at 23:08
  • $\begingroup$ OK. I took the liberty of editing in a link. $\endgroup$ – Gerry Myerson Feb 27 at 1:38
  • $\begingroup$ Are there any particular reasons to believe that "there are some corrections still to be made" in my post? If so, could you share them with me so that I can correct whatever is wrong? Otherwise, would you kindly delete the corresponding sentence from your post? $\endgroup$ – Seva Feb 28 at 11:12

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.