0
$\begingroup$

let $n \in \mathbb{N}$. Is is possible to find a sequence $S = \{ s_1, \dots, s_{n+k} \}$ ($k \leq n$) with a polynomial algorithm, so that for every pair $(x,y) \in S \times S$, the products $x \cdot y$ are pariwise distinct? Also $s_i \in S$ should be polynomial bounded with respect to $n$.

Regards,

Kreschew

  • 1
    Crossposted on http://mathoverflow.net/questions/73167/sequence-with-a-special-property2011-08-21

2 Answers 2

1

How about the prime numbers? They are poly bounded and computable.

Added: You can sieve up to $p$, giving about $p/\ln p$ primes in time $p \ln \ln p$, barely worse than linear. But we can do better yet in the sense of reducing the highest number in the set. Adding all numbers of the form $p^2,\ p^4,\ p^7,\ $ etc. will not spoil the fact that there are no matching products. I'm sure we can do better yet. If we know in advance how many we want, I think we can do better yet and will probably raise a new question.

  • 0
    @Kreschew: I don't think Bertrand's will get you $n$ polynomially bounded primes, but the prime number theorem will. It says there are about $n/\log n$ primes below $n$. I rounded up to say there are at least $n$ primes below $n^2$2011-08-19
1

The unique factorization property of the integers ensures that if you choose your set to contain only primes it will have this property (subjected to Andre's correction).