# Questions tagged [effective-results]

The effective-results tag has no usage guidance.

22
questions

**1**

vote

**0**answers

91 views

### Possible consequences in number theory and group theory if one-way functions exist explicitly? [closed]

It is known that the existence of one-way functions is an open and important problem in computer science. I read some of its implications, but it's still not clear at me what consequences we would ...

**1**

vote

**1**answer

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

**5**

votes

**1**answer

247 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

59 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

270 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

677 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

265 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_\...

**2**

votes

**2**answers

483 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

947 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

513 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

870 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

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

**10**

votes

**3**answers

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

**15**

votes

**4**answers

1k 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

595 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

1k 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 ...

**15**

votes

**6**answers

2k 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

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

**13**

votes

**2**answers

2k 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[\...

**2**

votes

**0**answers

980 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}...

**12**

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