Questions tagged [computational-number-theory]
Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.
476 questions
0
votes
0
answers
263
views
Computing the function field of a curve given as a subvariety of the Jacobian of its cover or merely the degree of the covering
I read following paragraph from:
G. Tamme, Teilkörper höheren Geschlechts eines algebraischen Funktionenkörpers, Arch. Math. 23 (1972), 257--259
Here $C$ is a curve of genus $\ge 2$ and $J$ is the ...
- 601
2
votes
1
answer
2k
views
How many cpus needed to check a 100 million digit prime number efficiently? [closed]
If I had access to potentially unlimited CPUs and wanted to quickly check 100 million digit numbers for primality using a map-reduce architecture, how many CPUs would be necessary? Each of the mapped ...
- 123
1
vote
0
answers
238
views
How to ask Magma to compute the induced morphisim on divisor group
Suppose Magma has computed homomorphism $h$ between function fields $F1 \to F2$. Then we have an induced homomorphism $h$ on the divisor group. Now my question is that if there's a better way to ...
- 601
8
votes
2
answers
485
views
Efficient computation of the least fraction with square denominator greater than the square root of 2.
The least rational number greater than $\sqrt{2}$ that can be written as a ratio of integers $x/y$ with $y\le10^{100}$ can be found in a moment using a little Python program. Can anyone write a ...
- 4,636
12
votes
1
answer
1k
views
How many LLL reduced bases are there?
For a given $n$-dimensional lattice embedded inside $\mathbb R^n$ along with a given inner product, how many distinct LLL-reduced bases are there?
In this question, a lattice is the set of all $\...
11
votes
0
answers
854
views
Points of bounded height in a number field
Let $K$ be a number field of absolute degree $d$, let $B$ be a positive real number, and write $S(K, B) = \{x \in K : H(x) \leq B\}$. Here $H$ is the absolute multiplicative height of an algebraic ...
- 1,199
5
votes
1
answer
750
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,...
- 9,114
1
vote
1
answer
1k
views
Computation for composition of polynomials
Let $R$ be a ring, $f(X)$ be a polynomial with coefficients in $R$ of degree $n$. It's known that for any $\alpha \in R$, one can evaluate $f$ at $\alpha$, i.e compute $f( \alpha) $ in $O(n)$ ...
- 2,179
4
votes
2
answers
713
views
Computing index of a subgroup of SL_2 in sage
Suppose I have a subgroup of $\textrm{SL}_2(\mathbb Z)$ given by 3 generators, and it happens to be of finite index in $\textrm{SL}_2$. Is there a way (on Sage, since that is what I have access to) ...
- 96.4k
4
votes
1
answer
14k
views
What is the longest known sequence of consecutive zeros in Pi? [closed]
Inspired by this question, I would like to know what is the longest known sequence of consecutive zeros in Pi (in base 10).
So far the longest I have found is the sequence of 8 zero's occurring in ...
CommunityBot
- 1
0
votes
1
answer
342
views
Necessary/Sufficient condition/Algorithm that tells me a function field is a kummer extension
I start my question with an example. Suppose $F/K$ be the function field generated by $x^n - yx^{n-1} - 1 = 0$. It is not a cyclic over K(y), but if I set $t = yx^{n-1}$ then we have $K(x,t) \subset K(...
- 601
4
votes
1
answer
708
views
Calculating the constant in the Bateman-Horn-Stemmler conjecture
Bateman & Horn [1], building on Bateman & Stemmler [2], give a conjectured formula for the density of numbers that produce simultaneous primes in a number of fixed polynomials.
The constant ...
CommunityBot
- 1
9
votes
3
answers
2k
views
Most efficient checking algorithm for Pell's Equation
What is the most computationally efficient way to check, given $x,y,D$ that they satisfy Pell's equation (positive or negative) ($x^2-Dy^2=1$)? (Obviously the question is concerned with very large ...
CommunityBot
- 1
14
votes
2
answers
1k
views
Subfields of a function field
Is there an algorithm for generating (some or all) subfields of a certain genus of a given function field (even a random one,I mean for example generating a random elliptic subfield of a certain given ...
- 116
9
votes
2
answers
756
views
Next (Restricted) B-Smooth Number Problem?
Given a bound, $B$, and a list of (small) primes $(p_0, p_1, \dots, p_{n-1})$ is there an efficient algorithm to find the next number greater than $B$ that can be expressed as a product of primes from ...
CommunityBot
- 1
3
votes
0
answers
713
views
Tunnell's theorem
Is it possible in some way, to use Tunnells's theorem to determine how long it will take a computer, to determine whether a number n, is a possible area of a rational right triangle?
- 8,467
7
votes
2
answers
732
views
Explicit map for Scholz reflection principle
The question is about the specific case of reflection theorems (copied straight from Franz Lemmermeyer's "Class Groups of Dihedral Extensions"):
Let $k^+ = \mathbb{Q}(\sqrt{m})$ with $m\in \mathbb{...
- 2,396
6
votes
1
answer
369
views
Speeding the quadratic sieve with an oracle
Suppose we have an odd composite $N$ and want to find numbers $a_1,\ldots,a_k$ such that each $a_i^2$, reduced mod $N$, is $b$-smooth. Of course we can use the quadratic sieve algorithm (minus the ...
- 4,593
1
vote
3
answers
509
views
Differences of squares
Suppose I wanted to express a number $N$ as a difference of squares. For large $N$ this is in general difficult, as finding $N=a^2-b^2$ leads to the factorization $N=(a+b)(a-b)$. Even if the problem ...
- 39.9k
12
votes
3
answers
881
views
What does the computer suggest about the parity of p(n), for n in a fixed arithmetic progression?
Let p(n) be the number of partitions of n. A famous theorem of Euler allows one to compute
the parity of p(n) quickly for quite large n. In:
On the distribution of parity in the partition function, ...
- 9,114
11
votes
1
answer
564
views
CM field to Torus to Abelian Variety?
Given a CM field we can use its maximal order (and a choice of CM type) to construct an abelian variety $\mathbb{C}^g/\Lambda$ with complex multiplication by the maximal order.
How do I (or where can ...
CommunityBot
- 1
3
votes
2
answers
876
views
on the computation of decomposition groups
Let $L/K$ be a finite Galois extension of function fields, with Galois groups $G$. I want to look at the ramification of primes in the extension, i.e. to get $e_p$ and $f_p$ for a prime $p$ in the ...
- 4,593
6
votes
2
answers
899
views
Enumerating representations of an integer as a sum of squares
Let $p$ be an odd prime. An old theorem of Jacobi asserts that $p$ has exactly $8(p+1)$ representations as a sum of four squares of integers (solutions counted with order and sign). What is the most ...
- 156k
5
votes
0
answers
228
views
Example of level one cuspidal Hecke Algebra T_k^0 such that p divides its index in its normalization, and p≥k-1?
The question is strongly focused on computations concerning modular forms and Hecke algebras. It is already in the title, but I will repeat it, adding a few details.
Let $S_k$ be the complex vector ...
- 2,406
10
votes
3
answers
650
views
Computationally bounding a curve's genus from below?
Background
In the course of answering another question (Infinite collection of elements of a number field with very similar annihilating polynomials) I found myself with a curve, that if it had a ...
CommunityBot
- 1
3
votes
2
answers
378
views
Upper bound on greatest prime of bad reduction for a plane curve
Background
We are given a curve with integer coefficients. I want to make a suggestion in another question (Computationally bounding a curve's genus from below?) into a deterministic algorithm ...
CommunityBot
- 1