Questions tagged [computational-number-theory]
Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.
159
questions with no upvoted or accepted answers
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 ...
- 40.8k
15
votes
0
answers
337
views
Do primes of the form $4k+1$ ever lead the greatest prime factor race?
Analogous to Chebyshev's race between primes, I examined the race between primes in the greatest prime factors, GPF, of natural numbers. Similar to the regular prime race, in the GPF race, the ...
- 4,638
13
votes
0
answers
1k
views
Why am I unable to find primes of the form $(9n)!+n!+1$?
See also Math StackExchange: Is there a prime of the form $(9n)!+n!+1$?
Recently, user Peter from Math StackExchange asked for a prime of the form $(9n)!+n!+1$ (where $n$ is some natural number).
...
- 1,316
12
votes
0
answers
1k
views
Euler's totient function and Riemann hypothesis
I am looking for an upper-bound of the Euler's totient function $\varphi$ which would be equivalent to the Riemann hypothesis (RH). There is the following Nicolas' criterion about primorial numbers $...
11
votes
0
answers
765
views
Borderline Collatz-like problems
The usual Collatz map is $C:n \mapsto n/2$ if $n$ even, $(3n+1)/2$ if $n$ odd. Let $f^{\circ (r+1)}:=f \circ f^{\circ r}$.
We suspect that for every fixed $n>0$, the sequence $C^{\circ r}(n)$ ...
11
votes
0
answers
826
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,169
8
votes
0
answers
232
views
Hilbert 10th problem for genus 2 equations
Hilbert 10th problem, while undecidable in general, remains open for 2-variable equations: we do not know if there is an algorithm that, for polynomial $P(x,y)$ with integer coefficients, decides ...
- 5,957
8
votes
1
answer
471
views
How large can the dimension of a 'Span of powers of a finite field basis' be?
Let $p$ be a prime. For finite field $\mathbb{F}_{p^k}$ and $d\in\mathbb{Z}^+$, I am considering the following quantity, where we interpret the field $\mathbb{F}_{p^k}$ also as a $\mathbb{F}_p$-vector ...
- 89
8
votes
0
answers
371
views
Computing motivic Galois group
Suppose I have a motive $M$ over $\mathbb{Q}$, and can compute the Euler factor of the associated $L$-function for any good prime $p$. How can I compute the Zariski closure of the image of the Galois ...
- 2,419
8
votes
0
answers
235
views
Computing the Moebius function $\mu$
Is it known whether computing $\mu(n)$ for a given integer $n$ is as hard as factorization?
- 19.4k
7
votes
0
answers
272
views
Are there infinitely many zeroes of $\sum_{r = 1}^{n-1} \mu(r)\gcd(n,r) $?
Let $\mu(n)$ be the Möbius function and $S(x)$ be the number of positive integers $n \le x$ such that
$$
\sum_{r = 1}^{n-1} \mu(r)\gcd(n,r) = 0
$$
My experimental data for $n \le 6 \times 10^5 $...
- 4,638
7
votes
0
answers
607
views
Proving Richardson's theorem for constants
(I asked this a little over 3 months ago on math.SE, and when I initially re-asked here, no one had responded there. $\:$ After I re-asked here, Eric Towers responded there, since I had forgotten to ...
user5810
7
votes
0
answers
293
views
On the ratio of Gilbreath sequences
Definitions: let $n \in \mathbb{N}_{>0} \cup \{ \infty \}$ and let $E_n$ be the set of sequences $(d_i)_{i=1}^n$ such that $d_1=1$, $d_i$ is an even integer (for $i > 1$) and $0<d_i \le i$. ...
6
votes
0
answers
191
views
Newton type method for finite fields?
I have a polynomial $p(x)$ in $\mathbb{Z}/q\mathbb{Z}$ that is easy to compute for any $x$ but has an absurdly large degree $d > 2^{256}$. I know for a fact that it has a zero and I would like to ...
- 581
6
votes
0
answers
109
views
Equivalence of primes based on the partition of their Pisano periods
The period of Fibonacci numbers modulo $m$ is called Pisano period and its length is denoted as $\pi(m)$. Define the Pisano partition of $m$ as the set partition of the indices $\{0,1,\dotsc,\pi(m)-1\}...
- 30.7k
6
votes
0
answers
159
views
Certificate for computation of ideal class group
Is there a known way of producing a certificate that can be used to more quickly verify that an ideal class group of a number field was computed correctly? More formally, I would like to know if there'...
- 1,806
6
votes
0
answers
90
views
Computing all eta quotients of given weight and level
I have written a rather naive program for finding all holomorphic eta quotients of
given weight and level (and varying character). When the level has few divisors it is
very fast, but incredibly slow ...
- 11.8k
6
votes
0
answers
288
views
Effective bounds for Fermat's Last Theorem
Suppose $n>2$. By Fermat's Last Theorem, we know that $a^{n}+b^{n}=c^{n}$
has no non-trivial solutions. Can we quantify it more?
More specifically, given $a,b,c,n\in\mathbb{N}$ with $n>2$ and $...
- 583
6
votes
0
answers
253
views
Brief history of primality testing theory after 2002?
Its clear that there is about 15 years (2004-2019) after the publication of AKS primality testing in 2002 and its modifications in 2003-2004. AS result, is there any development happened in this ...
- 199
6
votes
0
answers
427
views
Are there always at least *five* divisions?
@JosephO'Rourke asked a question about a Collatz like function related to primes:
$f(n) =
\begin{cases}
n^2 & \text{if} \;n \;\text{is prime} \\
\lfloor n/2 \rfloor & \text{if} \;n \;\text{...
- 1,345
5
votes
0
answers
175
views
Empirical bounds on $\left|\frac{\zeta'(1+it)}{\zeta(1+it)}\right|$
It is reasonable to expect that $$\left|\frac{\zeta'(1+it)}{\zeta(1+it)}\right| < 2 \log \log t$$
for all $t\geq 4$ (say): a somewhat stronger bound is known for $t\geq 10^{165}$ or so (Theorem 5 ...
- 19.4k
5
votes
0
answers
304
views
A question on infinite arithmetic progressions
I was working on a problem that consisted of deciding if the language a finite automaton (the alphabet of which is $\{0,1\}$ and the words accepted are binary encoded positive integers) contains an ...
- 51
5
votes
0
answers
197
views
Ramsey Numbers for Integers
Erdos defined $f(n)$ to be the minimum $r$ such that there is an $r$-coloring of the positive integers less than $n$, wherein $n$ cannot be written as the sum of distinct monochromatic integers. ...
- 141
5
votes
0
answers
337
views
About a diophantine equation from group theory
Is there any set of odd primes $\{p_1, p_2,..., p_k\}$ and natural numbers $a_1,..., a_k$ such that the following equation satisfied:
$${p_1^{2a_1+1}+1 \over p_1+1}\times ....\times {p_k^{2a_k+1}+1 \...
- 1,168
5
votes
0
answers
173
views
Finding a presentation matrix with low dimension
Let $R=\mathbb Z[t^{\pm}]$ and $M$ a finitely generated $R$-module. With $A$ a presentation matrix, i.e we have the following exact sequence (usually I'm working with the case where $A$ is an square ...
5
votes
0
answers
195
views
Is there some computational evidence of the $pq$ analog of Serre's conjecture?
The $pq$ analog of Serre's conjecture (see "Mod pq Galois representations and Serre's Conjecture"- Khare, Kiming) states that if $\bar{\rho}_1:G_{\mathbb{Q}}\rightarrow \text{GL}_2(\mathbb{F}_p)$ is a ...
user130124
5
votes
0
answers
125
views
Anyone got two Galois reps to compare?
I've got a new criterion for comparing Galois reps which are four dimensional if we know the kernel of the residual representation mod $5$ (or any large odd prime) and the Sato-Tate groups (should be ...
- 2,419
5
votes
0
answers
711
views
Primitive element for a number field, and ramification
Let $K=\mathbb Q(\theta)$ be a number field with integral primitive element $\theta$, and let $f(x)$ be the minimal polynomial of $\theta$. Let $p$ be a rational prime. It's well known that if $p$ ...
- 1,001
5
votes
0
answers
153
views
On factorization algorithms for $\mathcal{O}[x]$
We know that $\mathsf{LLL}$ algorithm provides factorization procedure that runs in poly time for polynomials in $\Bbb Z[x]$ that are primitive.
What other rings $\mathcal{O}$ can we use instead of $\...
user76479
5
votes
0
answers
286
views
Lower bound for p-adic distance between roots
Let $f$ be a formal power series with coefficients in the ring of integers of a finite extension of ${\mathbb Q}_p$. Is there a simple algorithm to compute a positive lower bound for $|\alpha - \beta|...
- 4,123
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,386
4
votes
0
answers
741
views
One of the numbers $\zeta(5), \zeta(7), \zeta(9), \zeta(11)$ is irrational
I am reading an interesting paper One of the numbers ζ(5), ζ(7), ζ(9), ζ(11) is irrational by Zudilin. We fix odd numbers $q$ and $r$, $q\geq r+4$ and a tuple $\eta_0,\eta_1,...,\eta_q$ of positive ...
- 1
4
votes
0
answers
42
views
Computing preimage of element under norm map of quadratic extension of $2$-adic fields
Let $F$ be a $2$-adic field, i.e. a finite extension of the $2$-adic numbers $\mathbb{Q}_2$. Suppose that I have a quadratic extension $E = F(\sqrt{d})$ of $F$. Given a unit $\alpha \in \mathcal{O}_F^\...
- 367
4
votes
0
answers
296
views
Are there infinitely many simple integral fusion rings of rank $4$?
$\DeclareMathOperator\ch{ch}$$\DeclareMathOperator\FPdim{FPdim}$We refer to [EGNO15, Chapter 3] for the notion of fusion ring and basic results. The type of a fusion ring $R$ is the list $(\FPdim(b_i)...
4
votes
0
answers
122
views
Road map for learning about the computational/general theory of modular curves/isogenies of abelian varieties for cryptography
I am a graduate math/crypto student. So I've had some free time last year and I heard about elliptic curves in cryptography and how a resilient cryptosystem got demolished by a spectacular attack ...
- 41
4
votes
0
answers
184
views
What are the modularity conjectures for Artin motives?
Classically, singular cohomology is an important tool for studying topological spaces, in particular, complex varieties. In the mid-twentieth century it was realized that there are many analogues of ...
- 509
4
votes
0
answers
123
views
Lattice reduction of basis with non-integer coefficients
Suppose I have an ordered basis $\{b_1, \dots, b_n\}$ of a lattice in $\mathbb{R}^n$, but I do not assume that $b_i \in \mathbb{Z}^n$ for all $1 \leq i \leq n$.
I would like to perform lattice ...
- 554
4
votes
0
answers
101
views
Questions in number theory related to $NC$ and $P$-completeness
Given $a,b\in\mathbb N$ find $\operatorname{GCD}(a,b)$.
Given $a,b,c\in\mathbb N$ find $x,y\in\mathbb Z$ such that $ax+by=c$.
Euclidean algorithm solves both.
My question is if either 1 or 2 is in ...
- 13.7k
4
votes
1
answer
282
views
Find $\mathbb{Z}$-basis of module over Dedekind domain provided its pseudobasis
Let $K$ be number field of degree $d$. Suppose we are given module $
\mathcal{M}$ in form:
\begin{equation}\label{key}
\mathcal{M} = v_1 \cdot \mathfrak{a}_1 \oplus v_2 \cdot \mathfrak{a}_2 \...
4
votes
0
answers
99
views
Reconstructing coefficients of an elliptic curve L-series from the modular form divisor
Let $E$ be an unknown elliptic curve over $\mathbb{Q}$.
Let $L(E, s) = \sum_{n=1}^{\infty} \frac{a_n}{n^s}$ be the L-function of $E$ and write $f(q) = \sum_{n=1}^{\infty} a_n q^n$.
I'm in a setting ...
- 5,517
4
votes
0
answers
142
views
Riemann-Siegel formula for Dirichlet characters
After unearthing and giving a proof of what is now known as the Riemann--Siegel formula for the Riemann zeta function enabling the computation of $\zeta(1/2+iT)$ in time $O(T^{1/2})$,
in 1943 Siegel ...
- 11.8k
4
votes
0
answers
210
views
What is the complexity class of this problem without Cramer's conjecture?
The problem 'Given $0<a<b$ is there a prime in the interval $[a,b]$?' is in $\mathsf{NP}$. If we assume Cramer's conjecture the problem is in $\mathsf{P}$ since if $b-a>(\log a)^{2+\epsilon}$ ...
- 13.7k
4
votes
0
answers
429
views
The irrational numbers α such that n odd and m=⌊nα⌋ odd implies ⌊mα⌋ odd
This post is the analogous of that one (about $\sqrt{2}$) but with a much stronger expectation here.
We observed, and then this comment of Lucia proved, that for $\phi$ the golden ratio, if $n$ ...
4
votes
0
answers
186
views
How to find a CM point with the image in the elliptic curve under modular parametrization given
everyone! Let $E:y^2+y=x^3-61$ be the minimal model of the elliptic curve 243b. How can I find the CM point $\tau$ in $X_0(243)$ such that $\tau$ maps to the point $(3\sqrt[3]{3},4)$ under the modular ...
- 338
4
votes
0
answers
118
views
Finding short linear combinations in abelian groups
Let $M$ be a finitely generated abelian group. Assume we are given a presentation of $M$, that is
\begin{equation*}
M = \frac{\bigoplus_{i=1}^r \mathbf{Z}g_i}{\sum_{j=1}^s \mathbf{Z} r_j}
\end{...
- 20.5k
4
votes
0
answers
274
views
Parity of number of primes
In https://arxiv.org/abs/1009.3956 is it shown there is a $c>0$ such that $\pi(x)\bmod2$ can be computed in $o(x^{\frac12})$ time (more precisely number of primes $\bmod 2$ for an interval of ...
- 13.7k
4
votes
0
answers
176
views
Computing the density of a set of multiples
Erdős and his coauthors often wrote about problems relating to the densities of sets of multiples. I have a computational question about the same topic. I have a finite* set $A=a_1<\cdots<a_r$ ...
- 8,984
4
votes
0
answers
203
views
Monte Carlo variant of Hilbert's Tenth Problem
Let $k \in \mathbb{N}$. Given an algorithm $\mathcal{A}$ which takes
as argument a polynomial $P \in \mathbb{Z}[x_1,\dots,x_k]$ and either
returns true or false, we say that $\mathcal{A}$ works for $P$...
- 19.5k
4
votes
0
answers
245
views
Algorithm/denominators of elements of a rational affine space
I hope it's not a trivial question... Suppose I have a finite dimensional vector space $V$ over $\mathbb{Q}$ with a distinguished basis (in my case it's the $k$th graded piece of the free associative ...
- 8,244
4
votes
0
answers
159
views
Range of the least witness function
Let W(n) be a function from the positive odd composite numbers to the least positive b such that n is not a b-strong pseudoprime. W(n) exists for all numbers in its domain and its range is unbounded. ...
- 8,984