Questions tagged [effective-results]
The effective-results tag has no usage guidance.
25
questions
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-...
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 ...
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 ...
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 ...
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 ...
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 ...
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-...
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 ...
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 $\: \...
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_\...
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 ...
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 ...
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$ (...
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 ...
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 ...
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 ...
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,...
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 ...
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 ...
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 ...
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[\...
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}...
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 ...
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 ...