Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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



share|cite|improve this question
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… – Tsuyoshi Ito Aug 21 '11 at 19:06

2 Answers 2

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

share|cite|improve this answer

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.

share|cite|improve this answer
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 – 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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