Questions tagged [computational-number-theory]
Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.
477 questions
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 ...
- 601
7
votes
2
answers
1k
views
Recovering n from sigma(n)/n
For any positive integer $n$, we define
$$\sigma(n) := \sum_{d \mid n} d,$$
and
$$\delta(n) := \frac{\sigma(n)}{n} = \sum_{d \mid n} \frac{1}{d}.$$
Is there an (efficient) way to determine $\delta^{-1}...
- 6,614
27
votes
2
answers
2k
views
How to explicitly compute lifting of points from an elliptic curve to a modular curve?
Say $E$ is an elliptic curve over the rationals, of conductor $N$. There's a covering of $E$ by the modular curve $X_0(N)$, and if you rig it right then you can define this map over $\mathbf{Q}$: ...
- 41.4k
16
votes
4
answers
25k
views
Is there an efficient algorithm for finding a square root modulo a prime power?
Cipolla's algorithm http://en.wikipedia.org/wiki/Cipolla's_algorithm is an efficient algorithm for finding a square root modulo a prime number. Is there an efficient algorithm for finding a square ...
- 2,649
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?
- 31
12
votes
1
answer
869
views
Analytic lower bounds on the first sign change of pi(x) - li(x)?
There have been many results on the first sign change of $\pi(x)-{\mathrm{li}}(x)$: among others, Lehman, te Riele, Bays & Hudson, Demichael, Chao & Plymen, and most recently Saouter & ...
- 9,114
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 ...
- 513
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{...
- 4,593
5
votes
2
answers
477
views
Density stability; questions for those who like computer calculation
BACKGROUND: The question, which has its roots in a question asked on MO by O'Bryant, concerns the relative density of certain subsets, $B$, of ${\mathbb N}$ in congruence classes modulo a power of 2. ...
- 5,422
6
votes
1
answer
370
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 ...
- 9,114
1
vote
3
answers
511
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 ...
- 9,114
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, ...
- 5,422
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 ...
- 4,593
4
votes
1
answer
414
views
Computing places over x in F/K(x)
Let $F$ be a function field of "transcendental degree one" over its full constant field $K$. Let $x \in F \backslash K$. We know the divisor of $(x) = (x) - (1/x)$ in $K(x)$. Could you please give me ...
- 601
11
votes
1
answer
2k
views
Integer values of a rational function
Suppose we are given a rational function with numerator and denominator being polynomials with integer coefficients. Is there an efficient algorithm for finding all integers arguments at which the ...
- 34.4k
3
votes
2
answers
877
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 ...
- 249
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 ...
- 13.1k
5
votes
4
answers
866
views
Reconstructing a fraction from its first digits
It is not difficult to see that any reduced fraction $\frac{p}{q}$
where $0 < p < q $ and both $p$ and $q$ have at most $N$
digits (where $N$ is a fixed integer) can be reconstructed
from its ...
- 3,595
15
votes
3
answers
3k
views
Finding zeroes of classical modular forms
There are several papers which compute zeroes of modular forms for genus 0 congruence subgroups, such as "Zeros of some level 2 Eisenstein series" by Garthwaite et al published in Proc AMS and work of ...
- 419
68
votes
7
answers
5k
views
Open project: Let's compute the Fourier expansion of a non-solvable algebraic Maass form.
OK so let's see if I can use MO to explicitly compute an example of something, by getting other people to join in. Sort of "one level up"---often people answer questions here but I'm going to see if I ...
- 41.4k
44
votes
5
answers
24k
views
Does pi contain 1000 consecutive zeroes (in base 10)?
The motivation for this question comes from the novel Contact by Carl Sagan. Actually, I haven't read the book myself. However, I heard that one of the characters (possibly one of those aliens at ...
- 32.1k
18
votes
0
answers
899
views
Computation of low weight Siegel modular forms
We have these huge tables of elliptic curves, which were generated by computing modular forms of weight $2$ and level $\Gamma_0(N)$ as N increased.
For abelian surfaces over $\mathbb{Q}$ we have very ...
- 41.4k
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
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 ...
- 4,593
10
votes
3
answers
652
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 ...
- 4,593
26
votes
3
answers
16k
views
How good is Kamenetsky's formula for the number of digits in n-factorial?
In Number of digits in n!, now closed, there was a mention of Dmitry Kamenetsky's formula, $[\bigl(\log(2\pi n)/2+n(\log n-\log e)\bigr)/\log 10]+1$, for the number of decimal digits in $n$-factorial. ...
- 39.9k
2
votes
2
answers
513
views
Unique representation of constructible numbers
I am interested in programmatically working with constructible numbers (the closure of the rational numbers under square roots). In order to perform comparisons between numbers I believe I would need ...
- 757