5
$\begingroup$

Let $d$ be fixed positive integer. For an integer $n$ consider a function $f_n: 2^{[d]} \to \mathbb{N}$ defined by $f_n(S) = \prod_{i \in S}(n + i)$. I'm interested in the smallest value $n_0(d)$ such that for any $n \geq n_0(d)$ the function $f_n$ is injective. In other words, $n_0(d)$ is the threshold on $n$ so that any subset of $[n + 1, n + d]$ should be reconstructible by the product of its elements.

Q: what are good bounds on $n_0(d)$? Both lower and upper bounds are interesting.

One easy upper bound is $n_0(d) = O(d!)$, since for $n > c \cdot d!$ we can look at digits of $f_n(S)$ in $n$-ary system to obtain the coefficients of the polynomial $\prod_{i \in S}(x + i)$. If we use balanced $(n + d / 2)$-ary system, we can lower the bound to $n_0(d) = O(((d / 2)!)^2)$. It appears $n_0(d) = O(d^c)$ or even $O(d)$ should be possible.

One lower bound would be $n_0(d) \geq d/2 + O(1)$, provided by a set containing $k, k + 1, 2k, 2k + 2$ for $k \sim d / 2$. Later edit: comments have examples that show $n_0(d) = \Omega(d^3)$, it's interesting if the method can be generalized.

Improve this question
$\endgroup$
4
  • $\begingroup$ Any product that has a prime factor q greater than d will single out that multiple of q in the interval. So non unique products will be d-friable numbers, and there aren't that many in an interval of length d. Indeed, I think you can replace d! by lcm(1..d) in your upper bound by adapting an argument of Langevin. This relates to Grimm maps and jumping primes. Gerhard "Check Out MathOverflow Question 243490" Paseman, 2020.04.02. $\endgroup$
    – Gerhard Paseman
    Commented Apr 3, 2020 at 0:06
  • 1
    $\begingroup$ An example of $k^2; (k+1)^2, (k+2)^2$ and $k(k+1),(k+1)(k+2),k(k+2)$ shows that $n\geq d^2/16+O(1)$. $\endgroup$
    – Ilya Bogdanov
    Commented Apr 4, 2020 at 20:43
  • 1
    $\begingroup$ @IlyaBogdanov Nice! We can also have $(k^3 - 16k)(k^3 - 7k - 6)(k^3 - 7k + 6) = (k^3 - 4k)(k^3 - 13k - 12)(k^3 - 13k + 12) = (k - 4)(k - 3)(k - 2)(k - 1)k(k + 1)(k + 2)(k + 3)(k + 4)$ for $n_0(d) = \Omega(d^3)$ for large enough $d$. I wonder if this can be generalized to show superpolynomiality... $\endgroup$
    – Mikhail Tikhomirov
    Commented Apr 5, 2020 at 3:23
  • $\begingroup$ Yes, I already came up with the same example. in order to proceed further, it suffices to find an $k\times k$ weak magic square (all row and column sums are equal) sich that the $i$th powers of the entries also form a weak magic square, for $i$ up to $k(1-\alpha)-1$. This provides $\Omega(d^{1/\alpha})$. In your example, $\alpha=1/3$. $\endgroup$
    – Ilya Bogdanov
    Commented Apr 5, 2020 at 7:15

1 Answer 1

Reset to default
1
$\begingroup$

One can beef up the lower bound a little bit. As an example, take a prime quadruplet such as 101,103,107,109. One has 11021*11009=10807*11227. If d is a little over 400 (421 in this case), $n_0$ can't be much smaller than (d/4)^2. One can try tight constellations of (more than 4) primes to improve asymptotically the exponent of the lower bound.

As observed in a comment, a non unique product must have all numbers involved lacking prime factors greater than d. A nice argument of Langevin maps a unique prime divisor to each member of [n+1,n+d] by using the largest prime power map: this works to provide an objective map when n is at least lcm(1..d), and can work for smaller values of n. Likely these prime powers can be used as tags to determine the presence or absence of a member forming a product of numbers in this interval. If so, this would give a tighter upper bound than d factorial on $n_0$.

Gerhard "Prime Powers Powering A Proposal" Paseman, 2020.04.02.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Indeed, one can replace primes in the quadruplet with arbitrary integers in a tight constellation, but it helps in thinking about this to choose a coprime set. This convinces me that a polynomial upper bound in d is not feasible for $n_0$. Gerhard "Use Bigger And Bigger Counterexamples" Paseman, 2020.04.02. $\endgroup$
    – Gerhard Paseman
    Commented Apr 3, 2020 at 5:33

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