4
$\begingroup$

I can deduce some results about this from the prime number theorem or from results about the primorial function $p\#$ but I'm wondering what the state of the art is:

Given integers $0\le a_1<a_2<\dots <a_c$, what bound can we put on the least modulus $m$ such that for all $i\ne j$, we have $a_i\not\equiv a_j$ (mod $m$)?

$\endgroup$
4
  • 3
    $\begingroup$ One cannot give any bound in terms of $c$ only, so I suppose you want a bound in terms of $a_c$? $\endgroup$
    – Seva
    Commented Feb 18, 2022 at 5:40
  • 2
    $\begingroup$ ... and it cannot be in terms of $a_c$ only since then you cannot give anything better than the trivial bound $a_c-a_1+1$ (consider $\{a_1,\dotsc,a_c\}=[0,a_c]$), correct? $\endgroup$
    – Seva
    Commented Feb 18, 2022 at 8:00
  • $\begingroup$ In terms of $a_c-a_1$ and $c$ I assume. $\endgroup$ Commented Feb 18, 2022 at 12:14
  • $\begingroup$ Right, right. In terms of $c$ and in terms of an $n$ with all $a_i<n$. $\endgroup$ Commented Feb 18, 2022 at 22:59

2 Answers 2

3
$\begingroup$

I'm not sure about the state of art, but here is a rough estimate in terms of $c$ and $\ell:=a_c-a_1$ in the case $c\ll \ell$.

First, we notice that for an integer $M$ satisfying $$M\# ~>~ \big(\frac{c}{2(c-1)}\ell\big)^{c(c-1)/2} ~\geq~ \prod_{1\leq i<j\leq c} (a_j-a_i),$$ where the second inequality follows from AM-GM, there exists a prime $m\leq M$ that does not divide the r.h.s.

Second, taking $M$ as smallest as possible and estimating primorial $M\#$ as $e^M$, we have $$m\leq M\approx \frac{c}2 + \frac{c^2}2\log\frac{\ell}2.$$ I believe this rough estimate can be made rigorous if needed.

$\endgroup$
4
  • $\begingroup$ Thanks, I didn't think of using AM-GM here, how are you doing that exactly? $\endgroup$ Commented Feb 18, 2022 at 17:52
  • 1
    $\begingroup$ @BjørnKjos-Hanssen: The arithmetic mean is $$\frac1{c(c-1)/2}\sum_{i\leq (c-1)/2} (c-1-2i)(a_{c-i} - a_{i+1}) \leq \frac{\ell}{c(c-1)/2} \sum_{i\leq (c-1)/2} (c-1-2i) \leq \frac{c}{2(c-1)}\ell.$$ $\endgroup$ Commented Feb 18, 2022 at 18:26
  • $\begingroup$ Great... much obliged $\endgroup$ Commented Feb 19, 2022 at 0:04
  • $\begingroup$ I see you also used that by L'Hôpital's rule, \begin{eqnarray*} \lim_{x\to\infty} x^2(\ln x-\ln(x-1))-x &=& \lim_{x\to\infty} \frac{\ln x- \ln(x-1)-1/x}{1/x^2} \\ &=&\lim_{x\to\infty} \left(\frac1x- \frac1{x-1}+\frac1{x^2} \right)\bigg/\left(-2/x^3\right)\\ &=&\lim_{x\to\infty} \left(\frac{1}{x^2(x-1)} \right)\bigg/\left(2/x^3\right)=1/2. \end{eqnarray*} $\endgroup$ Commented Feb 19, 2022 at 5:35
2
$\begingroup$

If $f(1),\ldots,f(n)$ are distinct integers, then the least positive integer $m$ such that $f(1),\ldots,f(n)$ are pairwise incongruent modulo $m$ is usually denoted by $D_f(n)$. There are some research papers studying $D_f$ (the discriminator of $f$) for various number-theoretic functions $f$, see the introduction of my 2013 JNT paper On functions taking only prime values. For example, I proved that if $f(k)=2k(k-1)$ for $k=1,2,\ldots,n$, then $D_f(n)$ is the least prime greater than $2n-2$.

If $f(k)$ is the product of the first $k$ primes, in the 2013 paper of mine I conjectured that $D_f(n)$ with $n>1$ is a prime smaller than $n^2$, and this was verified by W.B. Hart for $n=2,\ldots,10^5$.

Quite recently, Q.-H. Yang and L. Zhao (see arXiv:2111.02746) used Kloosterman sums to prove a conjecture of mine which states that the least positive integer $m$ such that $k^3+k\ (k=1,\ldots,n)$ are pairwise incongruent modulo $m^2$ is the least power of three no less than $\sqrt n$.

$\endgroup$
1
  • $\begingroup$ Thanks! These are rather specific integers but still, good to know. $\endgroup$ Commented Feb 19, 2022 at 4:06

You must log in to answer this question.

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