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
    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$?2011-08-18
  • 1
    Why talk about s_{n+k} and not s_{n}? I fail to see the role of k here.2011-08-18
  • 0
    Umm yeah, thank you, forgot about that ;). Should be $x < y$. So you have $0.5(n-1)n$ possible choices for pairs...2011-08-18
  • 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
    Yeah, I know. But I how can you find $n+k$ Primes in polynomiell time? '2011-08-18
  • 2
    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.2011-08-18
  • 0
    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 http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf.2011-08-18
  • 0
    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.2011-08-18
  • 0
    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$?2011-08-19
  • 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).