Questions tagged [computational-number-theory]
Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.
320
questions
17
votes
1answer
602 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 ...
4
votes
0answers
94 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 ...
-3
votes
1answer
205 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
1answer
116 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
vote
0answers
81 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^{\...
0
votes
0answers
79 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 ...
3
votes
0answers
170 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. ...
0
votes
0answers
53 views
Primality of $n$ bit integers in depth $n^\alpha$ under standard conjectures?
Denote $\mathsf{NC}(\mathsf{SUBLINDEPTH}(n),f(n))$ to be set of boolean circuits of fan-in $2$ which can be represented by depth $\cap_{\alpha>0}\mathsf{}n^\alpha$ and $f(n)$ sized Boolean circuits....
21
votes
1answer
718 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 ...
2
votes
0answers
77 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:
...
1
vote
0answers
45 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?
0
votes
1answer
62 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]$ ...
4
votes
0answers
191 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}$ ...
2
votes
0answers
96 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 ...
2
votes
0answers
37 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
vote
0answers
104 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 $...
24
votes
2answers
1k 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
2answers
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
1answer
73 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 ...
11
votes
1answer
244 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 ...
1
vote
0answers
148 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
0answers
45 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 ...
0
votes
0answers
29 views
Points of bounded height in Magma/Sage
Suppose I have an irreducible curve $C\subseteq \mathbb P^2_K$, where $K$ is a number field, given by some equation $f(x,y)=0$. Is there any Magma command to search for points up to a given height on $...
5
votes
1answer
237 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
1answer
626 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 ...
3
votes
1answer
127 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 ...
0
votes
0answers
90 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,...
7
votes
1answer
601 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 ...
5
votes
1answer
220 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 ...
3
votes
0answers
72 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 ...
2
votes
1answer
101 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:...
8
votes
1answer
378 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, ...
0
votes
0answers
21 views
Eigenvector of $U |y \rangle \equiv |xy (mod N) \rangle$, when $ x \le N$ and $x, N$ coprimes
In the book quantum computing and quantum computation of Nielsen and Chuang, in the chapter relating to order-finding, they say that via a simple calculation, an eigenvector of $U |y \rangle \equiv |...
5
votes
0answers
293 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 \...
2
votes
2answers
359 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 ...
2
votes
0answers
208 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 ...
6
votes
1answer
172 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
1answer
85 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
$$
5
votes
3answers
1k 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
votes
0answers
76 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 ...
1
vote
1answer
191 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)...
2
votes
0answers
75 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?
1
vote
1answer
184 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 ...
1
vote
2answers
91 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 $\...
2
votes
0answers
115 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-...
1
vote
0answers
83 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 ...
3
votes
1answer
324 views
Efficient computation of $\sum_{i=1}^{\sqrt{n}} i^2\cdot\left\lfloor{\frac n{i^2}}\right\rfloor$
I need to compute efficiently the sum
$$
\sum_{i=1}^{\sqrt{n}} i^2\cdot\left\lfloor{\frac n{i^2}}\right\rfloor.
$$
We can do this in $O({\sqrt{n}})$ but I need a faster algorithm: for example, it ...
6
votes
0answers
81 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 ...
1
vote
0answers
73 views
Digit summation of squared numbers
In olympiad teaching period, we have a session that students must try to design a good problem for others. Many times we arrive to good questions but sometimes there are some challenges. In one of our ...
2
votes
0answers
304 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$ ...
