Questions tagged [computational-number-theory]
Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.
477 questions
0
votes
1
answer
488
views
How to simulate Poisson point process
How to simulate a process $S_t=\sum_{0\leq s\leq t}\Delta_s,$ where $\Delta_s$ is a Poisson point process with values in $(0,\infty)$ and with characteristic measure $\Pi(dx)=\frac{\alpha}{\Gamma(1-\...
- 165
5
votes
0
answers
180
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,856
3
votes
0
answers
97
views
Study of relative class number of 'non-abelian' CM field by using L-functions
I'm currently interested in finding good upper bounds for the relative class numbers of non-abelian CM-fields.
So I'm looking for some references to learn the techniques that can be useful.
So far, I ...
- 1,013
2
votes
0
answers
207
views
Sum of all primes below $n$ without listing all primes below $n$
Asymptotically there is around $\frac{n}{\ln n}$ primes below a given integer $n$. Thus $\frac{n}{\ln n}$ is a lower bound for the time complexity of any algorithm that at some point finds each prime ...
- 21
2
votes
2
answers
312
views
Coefficient field of a newform using Magma
It is well-known that, for a newform $f = \sum c_nq^n \in \Gamma_0(N)$, the coefficient field $K_f := \mathbb{Q}(a_1, a_2, a_3, \cdots )$ is a number field.
I am introducing myself in Magma, and I was ...
- 29
20
votes
1
answer
1k
views
Possible contemporary improvement to bounded gaps between primes?
In his summary of his book Bounded gaps between primes: the epic breakthroughs of the early 21st century, Kevin Broughan writes
Which brings me to my final remark: where to next in the bounded gaps ...
- 35.5k
4
votes
0
answers
154
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 ...
- 13.1k
-2
votes
1
answer
494
views
Why wolfram alpha gives integers solutions for some equations of the form $ x^3 +(k\times10^n)^3 + z^3=0 $?
I have tried to get representations of some integers as sum of three cubic of the form $x^3+(k*10^n)^3+z^3$ with $k$ is integer and $n$ is a postive integer, I took this example : $(48807585839879)^3-(...
3
votes
1
answer
272
views
Connecting different ways of constructing cubic extensions of $\mathbb{Q}$
There are at least two ways to construct cyclic cubic extensions of $\mathbb{Q}$ as explained below. (A third one is given in the answer to an earlier question).
Given $A, B, C$ integers with $A\neq ...
- 1,566
1
vote
0
answers
96
views
Smooth number pairs satisfying a congruence
Let $\mathcal P=\{p_1,\dots,p_{2t}\}$ be $2t$ primes between $2^\ell$ and $2^{\ell+1}$ and fix an exponent bound $a\in\mathbb Z_{\geq2}$.
Fix $N\in\mathbb N$ whose prime factors $p$ satisfy $p>2^{\...
- 13.9k
0
votes
0
answers
149
views
How to determine if a unramifed prime split or not?
Let $K$ be the Number field and $L$ be finite extension where $\mathfrak{p}$ prime of K is unramified. Are there any conditions on $\mathfrak{p}$ so that I can say $\mathfrak{p}$ splits completely in ...
- 743
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
22
votes
1
answer
1k
views
How to see that the determinant of this matrix is nonzero for all primes?
I'm trying to show that $\sum_{i = 0}^{p-2} (i+1)^{-1} t^{i+n}$ where $0 \leq n \leq p-2$ spans the vector space $\mathbb{F}_p[t]/(1-t)^{p-1}$ as a rank $p-1$ module over $\mathbb{F}_p$.
In other ...
- 3,539
5
votes
1
answer
237
views
On a result of Euler on pseudoprimes
In several sources (for instance on page 58 of the first ed. of Crandall & Pomerance book on prime numbers or at the end of this paper by J. H. Jaroma), I have seen a result that goes like this:
...
- 87
1
vote
0
answers
57
views
Hecke eigenvalues of Siegel Modular forms of level greater than two
I wish to compute Hecke eigenvalues of Siegel Modular forms of level greater than two using the software like SAGE OR MAGMA. Is it possible to do the same?
- 248
1
vote
1
answer
92
views
What are the complexity classes of these problems about divisibility and coprimality?
The problems
'Given $0<a<b$ and a prime $p<a$ is there an integer $\ell\in[a,b]$ such that $p|\ell$?'
'Given $0<a<b$ and an integer $q\not\in[a,b]$ is there an integer $\ell\in[a,b]$ ...
- 13.9k
4
votes
0
answers
213
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.9k
2
votes
0
answers
110
views
Evidence of optimality of sieve algorithms
Sieve techniques apply to integer factoring and discrete logarithm to provide $2^{O(((\log n)(\log\log n)^2)^{1/3})}$ complexity for $n$ bit factoring and $n$ bit prime discrete logarithm.
The state ...
- 13.9k
2
votes
0
answers
54
views
Asymptotic growth of the collection of Miller-Rabin pseudo-primes witnessed by a set
Consider a set $S$ of positive integers[*]. Define $P(S)$ as the set of numbers $N$ for which elements of $S$ are "witnesses" for the Miller-Rabin test for primality of $N$. Explicitly $P(S)=...
- 1,566
1
vote
0
answers
139
views
Diophantine approximation and the Euclidean algorithm
My question is whether something I've noticed is well-known. It seems like it must be, but I've been unable to find any references that describe what is outlined below.
Given real $x$ and irrational $...
- 133
-1
votes
1
answer
342
views
Finite or polynomial number integral points clarification on Coppersmith's theorems (possibility of ellipse counter example?)
Coppersmith states if $f(x,y)$ is an irreducible bivariate with total degree $\delta$ then if he can list all roots $(X,Y)$ of the polynomial in $\mathsf{poly}(\log D,\delta)$ time if the roots ...
- 13.9k
25
votes
2
answers
2k
views
Do these rational sequences always reach an integer?
This post comes from the suggestion of Joel Moreira in a comment on An alternative to continued fraction and applications (itself inspired by the Numberphile video 2.920050977316 and Fridman, ...
8
votes
2
answers
1k
views
Fermat's last theorem $\pm1$
I'm planning a challenge over on Code Golf.SE about integers $a, b, c \ge 0$ such that
$$a^n + b^n = c^n \pm 1$$
for a given integer $n > 2$. However, I'm interested in whether any non-trivial ...
2
votes
1
answer
196
views
Software for $S$-unit equation
Is there any implementation available of an algorithm which solves in full generality the $S$-unit equation $x+y=1$ in a number field? It seems that Magma solves $ax+by=c$ but only in the algebraic ...
- 509
11
votes
1
answer
278
views
4-cliques of pythagorean triples graph and its connectivity
Let natural numbers $a, b > 2$ be adjacent if $|a^2 - b^2|$ is a square number. One can find a 3-clique.
For example 153, 185, 697. The questions are: does there exist a 4-clique? Is this graph ...
- 333
1
vote
0
answers
192
views
Integer solutions of Diophantine equation $y^2= 1+4n^{\underline k} $
I am looking for the integer solutions for the diophantine equation $y^2 =4n(n-1)(n-2)\cdots (n-k+1)+1$ for a given $k$ where $n>k+1>5$.
In other words,
$$y^2=1+4n^{\underline k},\tag{I}$$
where ...
3
votes
0
answers
73
views
Reference: Asymptotic bit-complexity of algebraic operations and transcendental functions
This question is a reference request. Does anyone know of a reference that lists the asymptotic bit-complexity of algebraic operations and transcendental functions implemented on a Turing machine that ...
- 131
2
votes
0
answers
96
views
Geometry for an odd perfect number? (Second question)
Let $e_d$ be the $d$-th standard-basis vector in the Hilbert space $H=l_2(\mathbb{R})$.
Let $h(n) = J_2(n)$ be the second Jordan totient function.
Define:
$$\phi(n) = \frac{1}{n} \sum_{d|n}\sqrt{h(d)}...
- 3,124
5
votes
1
answer
275
views
Is there a short proof for the permutation invariance of this combinatorial map?
Consider a positive integer $n$ and integers $(c_i)_{1\le i \le 4}$, with $1 \le c_i \le n$. Conside the map:
$$f_n: (c_1,c_2,c_3,c_4) \mapsto \delta_{c_1,c_2}\delta_{c_3,c_4} - \# \{ |2n+1-2|x||, \ x ...
9
votes
1
answer
858
views
Prove that there are no composite integers $n=am+1$ such that $m \ | \ \phi(n)$
Let $n=am+1$ where $a $ and $m>1$ are positive integers and let $p$ be the least prime divisor of $m$. Prove that if $a<p$ and $ m \ | \ \phi(n)$ then $n$ is prime.
This question is a ...
- 319
3
votes
1
answer
1k
views
Coppersmith bivariate polynomial roots implementation
Given $f(x,y)\in\mathbb Z[x,y]$ Coppersmith in https://link.springer.com/chapter/10.1007%2F3-540-68339-9_16 provides a provable method to find integer roots in polynomial time and this method was also ...
- 13.9k
0
votes
0
answers
110
views
Common integer roots of polynomials
I have two polynomials of form
$$f_1(w,x)=M_1$$
$$f_2(y,z)=M_2$$
and I have two polynomials of form
$$g_1(w,x,y,z)=M_3$$
$$g_2(w,x,y,z)=M_4$$
where $f_1,f_2,g_1,g_2\in\mathbb Z[w,x,y,z]$ and $M_1,M_2,...
- 13.9k
7
votes
1
answer
1k
views
Expressing primes $p\equiv 1 \pmod 3$ in the form $p = x^2 + xy + y^2$
Fermat famously showed that the only primes $p$ of the form $x^2 + y^2$ are the primes such that $p \equiv 1 \mod{4}$. Furthermore, we now know “effective” versions of Fermat's theorem, i.e. given a ...
- 1,703
6
votes
1
answer
243
views
Inductively computing Mersenne primes / perfect numbers?
For two sets $A,B$ set $A+B = \{a +b | a \in A,b \in B\}$.
Let $(x_n)_{n \in \mathbb{N}}$ be independent variables. Let $\sigma(n)$ be the sum of divisors of $n$.
Set $\hat{\phi}(1) = \{x_1\}$ and ...
user6671
3
votes
0
answers
81
views
I have a question on the definition of 'good' primes in the paper of Cohen and Martinet
I'm reading the paper of Cohen and Martinet 'Etude heuristique des groups de classes'.
In the section 6, for an central idempotent $e$ of $\mathbb{Q}[\Gamma]$ and a prime $p$, the 'goodness' of $p$ is ...
- 1,013
2
votes
1
answer
152
views
When can we decompose a multivariable p-adic power series into product of single variable power series?
Is there any known result of decomposing multivariable power series over $p$-adic field into product of single variable power series ?
For example, consider the following power series in $n$ variables:...
- 930
8
votes
1
answer
893
views
Is it possible to find a (nonsquare) integer which is a quadratic residues modulo a given infinite list of primes?
I'm wondering if it's possible, given a prime p and an infinite list of primes $q_1$, $q_2$, ... to find an integer d which (1) is not a square mod p, but (2) is a square mod $q_i$ for all i. Always, ...
- 121
5
votes
0
answers
339
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
2
votes
2
answers
648
views
A Pell like equation
If one takes in general $(\star)\, \,x^2-dy^2=C$ where $d$, $C$ in $\mathbb{N}$.
Taking $d=w^2p^2+p$ with $w\in \mathbb{Q}\ge 1$ and $p\in \mathbb{Z}$ which is verified (explained later), for the ...
- 785
2
votes
0
answers
288
views
Best known primality test for the whole intervals of integers up to $10^{20}$ — like the sieve of Eratosthenes
What are the best known primality test(s) for the whole intervals of integers up to $N=10^{20}$ ? "Best" means "have minimal amortized time per tested integer".
That is, the ...
- 121
8
votes
1
answer
328
views
On the density map of the abundancy index
Let $σ$ be the sum-of-divisors function. Let $σ(n)/n$ be the abundancy index of $n$. Consider the density map $$f(x) = \lim_{N \to \infty} f_N(x) \ \ \text{ with } \ \ f_N(x) = \frac{1}{N} \#\{ 1 \...
2
votes
1
answer
145
views
Estimation of a sum involving Stirling's number of second kind and binomial coefficient
Let $S(n, j)$ be Stirling's number of second kind. Let $p\in [0,1]$ and $m \in N$.
Bound from above the following sum:
$$
\sum_{j=0}^m S(n,j) {m \choose j}\, j! \, p^j
$$
- 97
5
votes
3
answers
2k
views
Goldbach conjecture and other problems in additive combinatorics
The field is also known as additive number theory. I am interested in sums $z=x + y$ where $x \in S, y\in T$, and both $S, T$ are infinite sets of positive integers. For instance:
$S = T$ is the set ...
- 3,098
3
votes
0
answers
110
views
Minimum of a product of polynomial evaluated at primitive roots of unity, given that the value of the polynomial at the same lies on unit circle
This is something that came out of working on a problem:
Let $m$ be an odd positive integer and $f \in \mathbb Q[x]$ be a polynomial of degree less than $m$. With $\zeta_m$ denoting a primitive root ...
- 739
1
vote
1
answer
218
views
On a quadratic diophantine equation
Given a quadratic diophantine equation in $\mathbb Z[x,y,z]$ of form
$$ax^2+by^2+cx+dy+ez+f=0$$ are there standard methods to solve for it when $$\|(x^2,y^2,z)\|_\infty\leq e^{1/2}$$
$$\|(a,b,c,d,e,f)...
- 1,836
2
votes
0
answers
93
views
Elementary Iwasawa module
Let $k$ be a given number field. What is the importance and applications of knowing that the Iwasawa module $X_\infty$ of $k$ is an elementary $\Lambda$-module?
- 21
2
votes
1
answer
456
views
Integrality certification for product of two matrices $A B^{-1}$
Let's consider two non-singular integer matrices $A,B \in\mathbb{Z}^{n\times n}$. I want a test to check if $A\times B^{-1}$ is integral (or no denominators). I am referring the unimodular ...
- 149
1
vote
2
answers
119
views
For a given value of $n$ and $m$, find $\text{fib}(n)$ $\text{mod } m$ where $n$ is very huge. (Pisano Period) [closed]
Input
Integers $'n'$ (up to $10^{14}$) and $'m'$(up to $10^3$)
Output
$\text{Fib}(n)$ $\text{modulo}$ $m$
My questions
For example : Why $\text{fib}(n=2015)$ $\text{mod}$ $3$ is equivalent to $\...
- 111
2
votes
0
answers
140
views
Double Diophantine approximation
Let $0 < \alpha < 1$. For any $n$ there is a closest lower Diophantine approximation $\max p / q \leq \alpha$ with integer $0 \leq p < q \leq n$. It can be found efficiently, e.g., with Stern-...
- 5,590
2
votes
0
answers
153
views
On the smallest solution of a linear congruence
I have the following question. First, consider the following congruence for primes $p\geq 5$:
$24x\equiv -1\;(\mbox{mod}\;p)$.
The smallest $x$, that is, $1\leq x\leq p-1$ for which the above ...
- 21