Questions tagged [effective-results]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4 votes
1 answer
130 views

Does the set of infinite random strings satisfy an analogue of immune sets?

Let $K(x)$ denote the Kolmogorov complexity of a finite binary string $x$. A finite binary string $x$ is called Kolmogorov random if $K(x) \geq |x|$. And an infinite binary sequence is called Martin-...
Keshav Srinivasan's user avatar
2 votes
1 answer
187 views

What fraction of the values of a quadratic polynomial can be prime?

I have an explicit, monic quadratic polynomial $P(x)$ and an integer $m$. Can I bound the number of prime values in $P(0), P(1), \ldots, P(m)$? A reference would be appreciated, if available. An ...
Charles's user avatar
  • 8,974
2 votes
0 answers
157 views

Degree of polynomials describing projection of algebraic set

Consider an algebraic subset $V\subseteq \mathbb{R}^{n+1}$ defined as the zero set of polynomials ${f_i}$ and the projection map $\pi: \mathbb{R}^{n+1}\to \mathbb{R}^n$ deleting the last entry. By the ...
BGJ's user avatar
  • 439
4 votes
0 answers
203 views

Effective bounds for a Bertini-type result

Suppose $X$ is a projective subvariety of $\mathbb{P}^n$ of codimension $r$ over $\mathbb{C}$, defined set-theoretically by $r$ homogeneous polynomials $P_1,\dots,P_r$ of degree at most $d$. By ...
Zeyu's user avatar
  • 537
1 vote
1 answer
162 views

Why is the relative trace of Sobolev norms finite?

I am reading the 2009 Paper on Effective Equidistribution by Einsiedler, Margulis and Venkatesh (EMV). I do not understand Section 5.3 on the proof of (3.10). They want to prove that the relative ...
Constantin K's user avatar
6 votes
1 answer
343 views

Friable Numbers In Short Intervals: Density Estimates?

I am hoping for explicit numerical estimates like the following sample (with made up numbers, though it might be true): for every $n \gt 10^6$ and every $b$ with $b^2 \lt n \lt b^3$, the number of ...
Gerhard Paseman's user avatar
3 votes
1 answer
65 views

Efficient evaluation of this correlation measure

What do you think would be the most efficient way of evaluating the following expression? Given a binary sequence $ E_N = (e_1,...,e_N) \in \{ -1,+1 \}^N $, and for $D = (d_1,d_2)$ with non-...
Mango's user avatar
  • 31
3 votes
1 answer
275 views

Time-efficient way of calculating the least number of 1s in a representation of $n$ using only the operations $+,!$

This was inspired by the following paper: J. Arias de Reyna, J. van de Lune, "How many $1$s are needed?" revisited, arXiv link. It might help explain my question better, because my question is ...
user avatar
7 votes
1 answer
765 views

Are there effective small intervals in which primes are dense?

As mentioned in Terry Tao's comment to this question, it is constructively known that there are primes between sufficiently large cubes. $\:$ According to wikipedia, "there exists a constant $\: \...
user avatar
2 votes
1 answer
380 views

Explicit bound on $\sum_{N\mathfrak p \leq x}\chi(\mathfrak p)\ln(N\mathfrak p)$

I'm looking for an explicit bound for $f(x) = \sum_{N\mathfrak p \leq x}\chi(\mathfrak p)\ln(N\mathfrak p)$, where $\chi$ is a Hecke character for a number field $K$ of degree $n$, on the ideals $I_\...
Calodeon's user avatar
  • 637
1 vote
2 answers
532 views

explicit large gap for consecutive zeros of the Riemann zeta function

In Theorem 9.12, Titchmarsh (The Theory of the Riemann Zeta Function) proved that For every large positive T, $\zeta(s)$ has a zero $\beta+i\gamma$ satisfying $$ |\gamma-T|<\frac{A}{\log\log\log ...
asd's user avatar
  • 163
4 votes
1 answer
1k views

effective/constructive/algorithmic probability theory

What sort of "alternative" probability theories are out there in which the methods of proof are inherently constructive? I know of a number of theorems that say that if you take an infinite sequence ...
James Propp's user avatar
  • 19.4k
9 votes
0 answers
551 views

Effective lower bound for class numbers of cyclotomic fields

Let $K=\mathbb{Q}(\mu_p)$ with class number $h=h^+h^-$, where as usual $h^+$ is the class number of the maximal real subfield of $K$. My question is whether there is an effective lower bound for $h$ (...
Jonah's user avatar
  • 171
8 votes
3 answers
1k views

Upper bounds on the difference of consecutive zeta zeros

There are many results on the spacing of the gaps between nontrivial zeros of the $\zeta$ function, from trivial (average value is $\frac{2\pi}{\log\gamma_n}$) to difficult (bounds on max and min ...
Charles's user avatar
  • 8,974
5 votes
1 answer
462 views

Determining the exceptional set in the theorem of Ax & Kochen

Ax & Kochen [1] proved that for every $d\in\mathbb{N}$ there exists a finite set $A(d)$ such that for every prime $p\not\in A(d),$ every homogeneous polynomial of degree $d$ over $\mathbb{Q}_p$ in ...
Charles's user avatar
  • 8,974
11 votes
3 answers
1k views

Density Ramsey theorems with explicit asymptotics

I wonder what interesting and non-trivial examples of density Ramsey theorems with explicit asymptotics are there? I'm aware of two examples: Szemerédi's theorem and density Hales-Jewett theorem. Let ...
16 votes
4 answers
2k views

Bounds on squarefree numbers

Let $q_1,q_2,\ldots$ denote the squarefree integers 1, 2, 3, 5, .... What effective bounds are known for $q_n$? Clearly $$q_n\sim\zeta(2)n$$ but I need hard inequalities. Of course from the above ...
Charles's user avatar
  • 8,974
5 votes
1 answer
721 views

Effective bounds on Euler's totient

Quick question: It's known that $$\limsup\frac{n}{\varphi(n)\log\log n}=e^\gamma$$ but are there known C and N such that $$\varphi(n)>\frac{Cn}{e^\gamma\log\log n}$$ for all $n>N$? Failing that,...
Charles's user avatar
  • 8,974
7 votes
2 answers
2k views

An effective way to tell if the saturation of a homogeneous ideal is the irrelevant ideal

Let $\Bbbk$ be an algebraically closed field, let $R$ denote the graded ring $\Bbbk[x_0, \dotsc, x_N]$, and let $f_1, \dotsc, f_n \in R_m$ be nonconstant homogeneous polynomials. Then the common ...
Charles Staats's user avatar
16 votes
6 answers
3k views

Advances and difficulties in effective version of Thue-Roth-Siegel Theorem

A fundamental result in Diophantine approximation, which was largely responsible for Klaus Roth being awarded the Fields Medal in 1958, is the following simple-to-state result: If $\alpha$ is a real ...
Stanley Yao Xiao's user avatar
6 votes
2 answers
1k views

Question related to Diophantine approximations and Roth's theorem

The following question came up in my arithmetic geometry course yesterday. Suppose $\alpha$ is an irrational real algebraic integer, and suppose $\epsilon >0$ is given. Then by Roth's theorem there ...
Ramin's user avatar
  • 1,362
14 votes
2 answers
3k views

Effective Chebotarev Density

Let $K$ be a number field, and $p$ be a rational prime. Then the Chebotarev Density Theorem implies we can find primes $v$ and $w$ of $K$ of degree 1 which are split and nonsplit respectively in $K[\...
Eric Larson's user avatar
  • 1,812
3 votes
0 answers
1k views

Effective upper bound on large prime gaps; or, what is the first prime after a googolplex?

Question What is the best known effective upper bound on the prime gap following x? Motivation Suppose you needed to show a good bound for the gap between a fixed large constant, say $G=10^{10^{100}...
Charles's user avatar
  • 8,974
13 votes
0 answers
1k views

Effective proofs of Siegel's theorem using arithmetic geometry

This is a speculation and perhaps naive. The theorem of Siegel that There exist only finitely many integral points on a curve of genus $\geq 1$ over a number ring $\mathcal O_{K, S}$ where $S$ is a ...
Anweshi's user avatar
  • 7,262
10 votes
1 answer
1k views

(Good) effective version of Kronecker's theorem?

Thm (Kronecker).- If all conjugates of an algebraic integer lie on the unit circle, then the integer is a root of unity. Question: Can one provide a good effective version of this? That is: given ...
H A Helfgott's user avatar
  • 19.3k