# Finding a sequence that has special properties

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

-
Need at least a small change, because if $(x,y)\in S\times S$ then $(y,x)\in S\times S$. Maybe additional condition $x \le y$? – André Nicolas Aug 18 '11 at 16:49
Why talk about s_{n+k} and not s_{n}? I fail to see the role of k here. – Gadi A Aug 18 '11 at 16:51
Umm yeah, thank you, forgot about that ;). Should be $x < y$. So you have $0.5(n-1)n$ possible choices for pairs... – Kreschew Aug 18 '11 at 17:15
Crossposted on mathoverflow.net/questions/73167/… – Tsuyoshi Ito Aug 21 '11 at 19:06

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).

-

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.

-
Yeah, I know. But I how can you find $n+k$ Primes in polynomiell time? ' – Kreschew Aug 18 '11 at 17:05
Well, there is a polynomial time algorithm for determining whether a given number is prime. So you'd just search for the next prime after the previous term of your sequence. Bertrand's postulate guarantees that you won't have to search too long. – Miha Habič Aug 18 '11 at 17:23
I'm not sure what the difference is between $n$ and $k$.There are at least $n+k$ primes less than $(n+k)$^2, and you can check each number in polynomial time-see cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf. – Ross Millikan Aug 18 '11 at 17:25
The AKS primality algorithm is an overkill. You can test whether an integer N is prime or not in time polynomial in N by trial division. The point of the AKS algorithm is that its running time is polynomial in log N. – Tsuyoshi Ito Aug 18 '11 at 23:24
Yeah, of course, thanks. So how do you apply Betrands theorem to find n prime numbers that are polynomial bounded with repect to n. Bertrand theorem only says that there is at least one prime between $n$ and $2n$? – Kreschew Aug 19 '11 at 1:46