Name
Abstract | ||
|---|---|---|
Given real numbers α1,...,αn, a simultaneous diophantine ε-approximation is a sequence of integers P1,..., Pn, Q such that Q j ∈ {1,...,n}, |Qαj-Pj| ≤ ε. A simultaneous diophantine approximation is said to exclude the prime p if Q is not divisible by p. Given real numbers α1,...,αn, a prime p and ε 0 we show that at least one of the following holds:(a)there is a simultaneous diophantine ε-approximation which excludes p, or(b)there exist a1,...,an ∈ ℤ such that Σajαj = 1/p + t, t ∈ ℤ and Σ|aj|≤n3/2|εNote that these two conditions are mutually nearly exclusive in the sense that in case (b) the aj witness that there is no simultaneous diophantine ε/ (n3/2p)-approximation excluding p. The proof method is Fourier analysis using results and techniques of Banaszczyk [Ban93].As an application we show that for p a prime and bounded d/p -- 1 the ring ℤ/pkℤ contains a number all of whose d-th roots (mod pk) are small.We generalize the result to simultaneous diophantine ε-approximations excluding several primes and consider the algorithmic problem of finding, in polynomial time, a simultaneous diophantine ε-approximation excluding a set of primes. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.5555/982792.982958 | SODA |
Keywords | Field | DocType |
diophantine approximation,fourier analysis,polynomial time | Prime (order theory),Diophantine set,Integer,Discrete mathematics,Combinatorics,Time complexity,Diophantine equation,Real number,Mathematics,Bounded function,Diophantine approximation | Conference |
ISBN | Citations | PageRank |
0-89871-558-X | 0 | 0.34 |
References | Authors | |
5 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Laszlo Babai | 1 | 3537 | 573.58 |
| Daniel Stefankovic | 2 | 243 | 28.65 |