Questions tagged [computational-number-theory]

Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.

Filter by
Sorted by
Tagged with
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$ ...

1
2 3 4 5
7