Questions tagged [computational-number-theory]
Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.
477 questions
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
4
votes
0
answers
182
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$ ...
- 9,114
9
votes
2
answers
647
views
On bounds for idoneal integer
What is the best known lower bound and upper bound known for such a number if it exists and have there been any attempts (computational including) to eliminate the existence of such a number in known ...
user76479
1
vote
1
answer
587
views
A quadrant of residues
Assume that following inequality holds $$\mathsf{w,x,y,z<AB,AC,AD,BC,BD,CD<ABC,ABD,ACD,BCD<wx,wy,wz,xy,xz,yz}$$ with $$\mathsf{gcd(A,B)=gcd(A,C)=gcd(A,D)=gcd(B,C)=gcd(B,D)=gcd(C,D)=1}$$
...
user76479
7
votes
1
answer
353
views
Numerically double-checking formula with L-values
I'm working with a special case of Ichino's triple product formula, which for classical holomorphic newforms $f$, $g$ ,$h$ of weights $k$, $m-k$, $m$ (and central characters satisfying $\chi_f \chi_g =...
- 131
0
votes
1
answer
665
views
A three variable linear diophantine promise problem
Given $a,b,c,s\in\Bbb N$ such that $(a,b,c)=1$ with promise that we have at most one triple $x,y,z\in\Bbb N$ such that $ax+by+cz=s$, what is a good algorithm that runs in $O(\log(abcs))$ time to find ...
user76479
3
votes
1
answer
457
views
On Pell's equation
A post was made (Reduction from factoring to solving Pell equation) seeking clarification to solving $$x^2-Dy^2=1$$ to factoring when $D>0$. An answer was posted stating that to factor $N$, it ...
- 13.9k
1
vote
1
answer
138
views
Runge-Kutta convergence [closed]
I am facing a problem solving a ODE with a Runge-Kutta 4th order method:
The expression in order to solve is :
\begin{equation}
Ay^{''}+By^{'}+Cy= Cu
\end{equation}
\begin{equation}
y =OUTPUT
\end{...
- 11
6
votes
1
answer
412
views
Computing an eigencuspform in $S_2(\Gamma_0(1776))$
Consider
$$\bar{\rho}:G_{\mathbb Q}\longrightarrow\operatorname{GL}_2(\mathbb F_7)$$
the residual 7-adic Galois representation attached to the elliptic curve $y^2=x^3+x^2-4x-4$ of conductor 48. Then $...
- 10.9k
6
votes
0
answers
448
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,375
15
votes
4
answers
2k
views
Computing minimal polynomials using LLL
I would like to use the Lenstra–Lenstra–Lovász lattice basis reduction algorithm (LLL algorithm) to compute the minimal polynomial of a (real) algebraic number $\alpha$ from a decimal approximation $a$...
- 3,165
2
votes
0
answers
166
views
algorithm to find a new point of small height in a number field extension
By the height of an algebraic number $\alpha$, I mean the absolute, logarithmic (additive) Weil height $h(\alpha)$; e.g. $h(2^{1/n}) = (\log 2)/n.$
If $K$ is a number field, let $\delta(K)$ denote ...
- 1,499
2
votes
0
answers
111
views
Comparing the size of two sums
Let $q$ be a prime power and $\mathbb{F}_q$ be the field of $q$ elements.
Let $\mathbb{F}_q[t]$ be the polynomial ring over $\mathbb{F}_q$.
I am working on a research project, where I bounded a ...
- 579
1
vote
1
answer
325
views
Error term for prime harmonic
What is known about the asymptotic behavior of
$$
f(x)=\sum_{p\le x}\frac1p-\log\log x-B_1?
$$
Of course by Mertens we know that $f(x)=o(1),$ but has more been proved (in terms of $O$ or $\Omega_\pm$,...
- 9,114
3
votes
1
answer
712
views
Residues and values of Riemann Zeta function at some points
I need the following computational results for proving something.
Let $1/2 + i\gamma_0$, be the first nontrivial zero of Riemann zeta function, $\zeta(s)$,
i.e. $\gamma_0\sim 14.134...$.
1) what is ...
- 897
4
votes
0
answers
206
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.6k
7
votes
0
answers
294
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$. ...
3
votes
1
answer
284
views
What is the ring $A_{\Gamma}$ in the Cohen-Lenstra Heuristics?
I understand the work in Cohen and Lenstra's paper that leads up to the heuristics themselves, where they count weighted averages of functions defined over isomorphism classes of $A$-modules, where $A$...
- 179
2
votes
1
answer
356
views
Computing all "suboptimal" rational approximations to $\pi/2$
I have an irrational number $\alpha$ ($\alpha=\frac\pi2$), and I would like to determine all integers $n\in[1,N]$ ($N=10^{16}$) that satisfy
$$ n \epsilon(n)^2 \leq \tau $$
where $\tau$ is a known ...
- 416
3
votes
0
answers
203
views
Fourier expansions of newforms at width-1 cusps
Let $f_E$ be the newform attached to the Elliptic Curve $E$ with cremona label
$\textbf{100a1}$ and let $\alpha = \left[\begin{matrix} 1&0 \\ 10&1 \end{matrix}\right] \in SL_2(\mathbb{Z})$. ...
- 221
1
vote
0
answers
415
views
Rings of algebraic integers as quotients of polynomial rings
The ring of integers $\mathcal{O}_K$ of a number field $K$ is always isomorphic to some ring of the form $\mathbb{Z}[x_1, ..., x_r]/\mathfrak{p}$, where $\mathfrak{p} \subset \mathbb{Z}[x_1, ..., x_r]$...
- 704
2
votes
3
answers
476
views
How to define the input of computable function or Turing machine over real numbers
Computation or computability over $\mathbb{N}$ can be extended to computation or computability over $\mathbb{R}$ or even computation or computability over $\mathbb{C}$.The following is a formal ...
- 3,104
13
votes
1
answer
2k
views
Erdős multiplication problem revisited
This is a well-known problem and is about counting the number of distinct numbers in the $n \times n$ multiplication table.
The very problem has been discussed in-depth and, as such, I require no ...
user56218
3
votes
0
answers
172
views
Algorithm to compute a common denominator of a finite set of rational numbers
Let $x_1,\dots,x_n \in \mathbb{Q} \cap (0,1)$ be fixed, but unknown, and assume that we know a number $K \in \mathbb{N}$ such that there is a number $N \in \{1,\dots,K\}$ such that $x_1 N,\dots,x_n N \...
- 811
19
votes
2
answers
2k
views
Is formula valid for relating $\pi$ with ALL of its OEIS A002485(n)/A002486(n) convergents?
Could anyone try to prove that the below conjectured formula is valid for relating $\pi$ with ALL of its convergents - those, which are described in OEIS via A002485(n)/A002486(n)?
$$(-1)^n\cdot(\pi - ...
- 335
2
votes
1
answer
121
views
Growth of the truncation of the integral multiples of an irrational number
Let $[a]$ denote the integral part of a real number $a$.
Let $a$ be an irrational number and $b$ a real number greater than $1$.
Consider the sequence $(b^n(na-[na]))$ with $n$ running on the ...
1
vote
2
answers
751
views
Computational complexity of solution of Pell equation and more
What is computational complexity for computing integral solution of Pell equation .It seems to be in P ,and could any one give an algorithm and reference for proof of it's complexity?
And more,could ...
- 3,104
0
votes
1
answer
130
views
Size of approximate solution of an integer relation
Let $X_1$, ..., $X_n$ be a list of real numbers.
Consider an integer relation equation
$A_1 X_1 + \ldots + A_n X_n = 0$
where $A_1$, ..., $A_n$ are unknown integers.
Suppose somehow we are not so ...
- 1
3
votes
1
answer
233
views
Calculating (n ^ fibonacci(k)) MOD m for a large value of k
The value of $k$ can be very large indeed (up to $10^{12}$). Is there an efficient way to calculate the output?
Edit : 'm' is a prime number.
2
votes
2
answers
413
views
Number Field Sieve for factorization with non-monic non-linear polynomial. Can't understand calculating ideal valuations
There is a paper "Factoring integers with the number field sieve" (download it here, for example).
I can't understand how they reason the correctness of computing ideal valuations in the case of ...
2
votes
0
answers
106
views
Is there any track for proving $D=NP$, besides showing that $D$ has polynomial-bounded universal quantifiers?
Background
By the MRDP theorem, every for every recursively enumerable set $S$, there exists a Diophantine polynomial $p$ such that
$$x \in S \iff \exists y_1, \dots, y_n \in \mathbb{N} \text{ such ...
- 1,389
6
votes
2
answers
994
views
Minkowski successive minima inequality for a lattice base?
Let $\Lambda$ be a lattice of $\mathbb{R}^n$, and $\lambda_i$ be the radius of the smallest ball containing $i$ linearly independent lattice vectors.
The Minkowski successive minima inequality says ...
- 403
1
vote
1
answer
353
views
Valid Difference Sets
Suppose
$$
P \subseteq \{1,2,\dots,N\},\quad |P| = K
$$
We calculate the differences as:
$$
d=p_i-p_j\mod N,\quad i\ne j
$$
Now let $a_d$ denote the number of occurrence of $d$ (for $d = 0, 1, 2, ...
- 123
2
votes
1
answer
387
views
Question on x coordinates of Mordell Curves where $y^2=x^3+k$ and $k^2 = 1$ mod $24$
In my ongoing search for Mordell curves of rank 8 and above I have currently identified 144,499 curves of a type where $k$ is squarefree and $k^2 = 1$ mod $24$.
In each case the x coordinates are ...
- 791
0
votes
1
answer
224
views
Spreading-out integers via multiplication
Let $a_1,...,a_n\in [0,m]$ be a set of $n$ positive integers, where $n<<m$, $m=poly(n)$.
One can assume $m$ is prime.
Is there an efficient, possibly randomized, way to find an integer $N=poly(n)...
- 445
2
votes
2
answers
510
views
On Cubic Non-Residues Modulo a Prime [closed]
What is a good test for identifying cubic non-residues/residues and higher power non-residues/residues modulo a prime $R$ in terms of computational complexity?
Given $M$ and $N$, is there a good way ...
- 13.9k
5
votes
3
answers
2k
views
Square root algorithm
I would like an efficient algorithm for square root of a positive integer. Is there a reference that compares various square root algorithms?
2
votes
0
answers
769
views
Textbooks on Algorithmic Number Theory
I am looking for a good textbook suitable for graduate or advanced undergraduate students who want to explore algorithmic number theory. Specifically, algorithms for primality testing, and factoring ...
- 575
0
votes
0
answers
461
views
Computational Ring Theory
I have tried to understand and program CGT algorithms though I am a beginner still. But I never get to hear Computational Ring Theory. Even GAP largely supports Groups Theory. Is there some initiative ...
- 133
4
votes
2
answers
517
views
Average involving the Euler phi function
Does
$$\frac{1}{N^2}\sum _{d=1}^N \log d \sum _{n=1}^{N/d} \frac{\phi(n)}{\log (dn)},$$
converges or not when $N$ goes to infinity?
- 43
4
votes
1
answer
354
views
Hejhal's algorithm and computational methods for non-classical Maass wave forms
Hejhal's algorithm [1] was a little gadget invented in the 90's for calculating the Hecke eigenvalues and Fourier coefficients of Maass wave forms. Later, Booker, Strombergsson, and Venkatesh (BSV) [2]...
- 309
11
votes
1
answer
565
views
When adding a constant makes a multivariate polynomial reducible?
Given a multivariate polynomial $f(x_1,\dots,x_n)$ with integer coefficients, how to find an integer $m$ (if it exists) such that $f(x_1,\dots,x_n) + m$ factors into polynomials of smaller degrees?
...
- 34.4k
1
vote
2
answers
337
views
Transformation of a bivariate polynomial into a homogeneous one
For a given a bivariate polynomial $P(x,y)$ with rational coefficients:
Q1. How compute such (invertible) substitutions of its variables that would transform the polynomial into a homogeneous one? In ...
- 34.4k
0
votes
2
answers
754
views
On reducible polynomials with positive coefficients, $1$ as constant coefficient and certain bounds on coefficients
Given $a \in \mathbb{Z}$ with $a > 1$. Let $g(x) \in \mathbb{Z}[x]$ be a polynomial with $g(a)=\pm 1$. Let $h(x) \in \mathbb{Z}[x]$ be a polynomial with $h(a)= p$, a prime. Let $g(x)$ and $h(x)$ ...
8
votes
1
answer
1k
views
Can a Hamkins infinite time Turing Machine with infinite Super Turing jumps (from higher type oracles) get the power to decide $\Sigma_1^2$ sets?
Hamkins showed that his infinite time Turing machine has the power to decide some $\Delta_2^1$ sets. I wonder if some modifications of the machine could be made to reach level $\Sigma_1^2$ sets, or, ...
- 297
2
votes
0
answers
305
views
Large numbers in small systems
Can we ever know the sum of the first $10^{10^{100}}$ digits of $\pi$?
Can we calgulate the $n$th digit of $\pi$ when the Kolmogorov-complexity of $n$ is larger than the complexity of the calculating ...
user112109
13
votes
3
answers
1k
views
Is there a composite number that satisfies these conditions?
We know that if $q=4k+3$ ($q$ is a prime), then $(a+bi)^q=a-bi \pmod q$ for every Gaussian integer $a+bi$. Now consider a composite number $N=4k+3$ that satisfies this condition for the case $a+bi=3+...
- 131
8
votes
3
answers
2k
views
Numerical evaluation of the Petersson product of elliptic modular forms
It is known how to compute the Fourier expansion of elliptic modular forms using modular symbols, and it is known how to get numerical evaluations of $L$-functions of various type ; it's possible to ...
5
votes
4
answers
792
views
Proving a least prime factor
Suppose that I find a small prime factor $p$ dividing a large number $n$ and I wish to prove that it is the least prime dividing $n$. There are two obvious approaches: either factor $n/p$, or divide $...
- 9,114
6
votes
1
answer
456
views
Solving equations in a subset of rational numbers
Let $S$ be a set of all positive rational numbers $x$ such that $2x^2 - 1$ is a square, excluding $x=1$.
I am interested in computing as many as possible solutions in $S$ to either the following ...
- 34.4k