Questions tagged [computational-number-theory]
Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.
448
questions
5
votes
2
answers
272
views
Computing the Abelian invariants of a subgroup of a f.g. Abelian group
We have a f.g. Abelian group $A$ given as a direct sum of $N$ cyclic subgroups $C_{k_j}=\langle x_j\rangle$, with $k_j\in \{2,\dots,\infty\}$, $1\leq j \leq N$, and the associated homomorphism $\phi:\...
- 13.7k
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
1
vote
0
answers
27
views
Time complexity of Magma's `NormEquation` for quadratic extensions of $2$-adic fields
Note: This is similar to, but easier than, a previous question I asked here. It is a different question! I'm hoping this one might get an answer because it concerns a standard algorithm, whereas the ...
- 367
16
votes
2
answers
1k
views
Is it decidable whether two real algebraic irrationals generate the same extension of the rationals?
For an algebraic number $\alpha$, let $f_\alpha$ denote its minimal polynomial. We can symbolically represent an algebraic number $\alpha$ by the tuple
$$
(f_\alpha, x, y, r) \in \mathbb{Q}[x] \times ...
- 1,035
2
votes
1
answer
137
views
Are the coefficients in the stationary phase approximation computed explicitly somewhere
In Stein's "Harmonic analysis" book, page 334, one can find
the asymptotic expansion
An instructive proof is given for the case $k=2$. It is clear enough to generalize to the cases $k\geq ...
- 744
2
votes
2
answers
745
views
Sum of three square is a square and sum of their product taken two at a time is also a square
Let $a^2 + b^2 + c^2 = X^2$ and
$$(ab)^2 + (ac)^2 + (bc)^2 = Y^2$$
Such that $a,b,c,x,y$ are all non zero Integers.
How to find All solutions ?
Is there any parametrization which gives Infinitely ...
- 47
1
vote
1
answer
84
views
Number of solutions for linear modular equations given GCD
We are currently investigating a problem involving number theory, an area outside our field of expertise.
Let $n$ be a positive integer. Consider two pairs of integers $(j,k)$ and $(j′,k′)$ as ...
13
votes
2
answers
1k
views
Using the Eichler-Selberg Trace formula to compute class numbers?
The Eichler-Selberg trace formula (Theorem 2.2 here) gives a relation between the trace of a Hecke operator acting on the space of cusp forms and sums of weighted class numbers of imaginary quadratic ...
- 133
4
votes
0
answers
43
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
3
votes
1
answer
188
views
Generators of the ideal class group
Theorem 4 of Eric Bach's "Explicit bounds for primality testing and related problems" states the following:
Let $K$ be a number field of degree greater than 1. Let $d$ be the absolute value ...
- 33
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
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)...
- 25.9k
1
vote
1
answer
290
views
Is there any way to estimate this functions: $f(n)=\sum_{d|n}d\varphi(d)$ and $g(n)=\sum_{d|n}\frac{\varphi(d)}{d}$?
Let that $n$ be a natural number and $\varphi(n)$ be the Euler totient function. Is there any formula or estimation for computing functions $f,g$ such that:
$$
f(n)=\sum_{d\mid n}d\varphi(d)
$$
and
$$
...
- 139
3
votes
2
answers
257
views
When I know the two points on an elliptic curve, and the two points satisfy the relationship: $Q=e \cdot P$, is it possible for me to solve for e [closed]
When I know the two points on an elliptic curve, and the two points satisfy the relationship: $Q=e \cdot P$, is it possible for me to solve for $e$.
The equation of the curve is: $y^2 = x^3 + ax + b \...
- 31
0
votes
1
answer
116
views
Integer quadratic representation subject to discriminant minimization algorithm
Let $f(x)=ax^2+bx+c$ and $f(x)=n$. Is there an algorithm to choose $a,b,c$ such that the discriminant is minimized? Where $a,b,c,n,x$ are all integers.
More concretely, is there an algorithm to find $...
0
votes
0
answers
59
views
What is the lattice point distribution over binary quadratic forms?
Let $f(x,y)=x^2+ny^2$ be the binary quadratic form of interest and consider the lattice points $S=\{ (x,y,f(x,y)) \in \mathbb{N}^3 \}$.
For simplicity, we keep things only on quadrant I of the ...
4
votes
3
answers
290
views
How to recover integer part from known fractional root part?
Suppose you have $r=n+f$ where $n\in\mathbb{N}$ and $f\in (0,1)$. I know that $r^2$ is an integer and I can also get as many digits of $f$ as I like, is there a way to recover the value of $n$?
Thank ...
3
votes
1
answer
286
views
Does this condition characterise intervals, among subsets of the real line?
For a real number, $c\in \left]0,1\right[$, consider the following property $\mathbf(\mathbf P_c\mathbf)$ of subsets $A$ of $\mathbb R$:
$\mathbf(\mathbf P_c\mathbf)$ For every bounded set $B\subset \...
- 56.6k
1
vote
1
answer
197
views
Calculating the value of periodic continued fractions with $a_i\in\lbrace 0,1\rbrace$
Question:
How can the value of continued fractions of the form
$$y:=a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\cfrac{1}{\begin{align}\ddots& \\ &a_{n-1}+\cfrac{1}{a_n+y}\end{align}}}}}$$
$$...
- 12.7k
2
votes
0
answers
63
views
Simultaneous computation of the three Weber modular functions
Recall that the three classical Weber modular functions are defined by
$f(\tau)=e^{-\pi i/24}\eta((\tau+1)/2)/\eta(\tau)$,
$f_1(\tau)=\eta(\tau/2)/\eta(\tau)$, and
$f_2(\tau)=\sqrt{2}\eta(2\tau)/\eta(\...
- 11.8k
9
votes
2
answers
2k
views
Can every integer be written as a sum of squares of primes?
This question is mainly inspired from a different problem I was working on.
Is there a value of $k$ such that, for each $n\in \mathbb N$, the equation
$$\sum_{i=1}^{k}x_i^2=n$$
is solvable in $x_1,\...
- 781
0
votes
1
answer
84
views
What can be said about $\gcd(N/q^{\alpha},\sigma(N/q^{\alpha}))$ where $N$ is an odd perfect number and $q^{\alpha} \parallel N$?
What can be said about the quantity $$\gcd(N/q^{\alpha},\sigma(N/q^{\alpha}))$$ where $N$ is an odd perfect number and $q^{\alpha} \parallel N$? In particular, can one prove that it is always greater ...
- 1,008
0
votes
0
answers
138
views
Positive definite quadratic form algorithm
Let $f(x,y)= ax^2+bxy+cy^2$, or similarly denote it by $(a,b,c)$. This question is about the case $(1,0,p)$ where $p$ is prime. Suppose I have one solution $\bar{x}_1=(x_0,y_0)$ for $f(x,y)=m$ for ...
2
votes
1
answer
249
views
A weird property of odd positive integers $n$ with $\sigma(n)\sim2n $
When one looks at positive odd integers $n$ for which $|\sigma(n)-2n|\le\log n$, (sequence A088012) it appears that for all seven known numbers of this type the abundance, $\sigma(n)-2n$ is $\equiv 6\...
- 388
4
votes
1
answer
198
views
Is there a Bailey–Borwein–Plouffe (BBP) formula for $\gamma$ (euler-mascheroni constant)?
I was reading about BBP type formulas and there was a lot about $\pi$ and some $\log$'s. I started searching for some other constants and could find $2$ formulas for the catalan constant and learned ...
- 521
2
votes
1
answer
298
views
Can you confirm the positivity of a quantity involving the Stirling numbers of the first kind
Let $s(m,n)$ denote the Stirling numbers of the first kind. For $m,n\in\mathbb{N}$, define
\begin{equation}
\mathcal{Q}(m,n)=(-1)^n\sum_{\ell=0}^{2n} \binom{m+\ell-1}{m-1} s(m+2n-1,m+\ell-1)\biggl(\...
- 838
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
0
votes
0
answers
181
views
Efficiently count the number of primitive roots in all moduli up to $n$
Let's define $f(n)$ as the number of primitive roots modulo $n$. That is, $f(n) = \begin{cases}\varphi(\varphi(n))&n=1,2,4,p^k,2p^k\\0&\text{otherwise}\end{cases}$. We want to efficiently ...
- 2,979
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
1
vote
0
answers
56
views
Condition on the minimality of Minkowski units
I am interested in to undrestand when the Minkowski units in real biquadratic number fields are minimal in the log unit lattices.
I have read some pieces of literature online which are investigating ...
- 11
0
votes
0
answers
331
views
Counting perfect powers using primes
Result
Let $n\in\mathbb{N}_{\geq1}$
$n$ is by definition a perfect power iff
$\,\ \exists m,k\in\mathbb{N}_{>1}:n=m^{\,k}$
Let $N(n)$ be the number of perfect powers $\leq n$
We define
$$\mathbb{...
- 53
0
votes
1
answer
107
views
Residues distribution modulo an interval
Given a number $n$ and an Interval $I = [ \; \lfloor n^{1/4} \rfloor, \lfloor n^{(1/3) \rfloor \;} ]$, can we say anything about the distribution of $\{ n \mod b \;\;| \; b \in I \}$?
In particular, ...
6
votes
1
answer
603
views
On a fast high precision numerical analysis C library
This is probably a $y=f(x)$ question, but I searched several times on the MathOverflow without success so I decided to explicitly ask for the help of other members: please feel free to ask me to ...
- 5,632
3
votes
1
answer
497
views
abc-conjecture and positive definite kernels, again?
One formulation of the abc-conjecture is:
$$\forall a,b \in \mathbb{N}: \frac{a+b}{\gcd(a,b)}< \operatorname{rad}\left ( \frac{ab(a+b)}{\gcd(a,b)^3}\right )^2 $$
Let us define:
$$K(a,b) := \frac{2(...
- 2,462
1
vote
0
answers
30
views
Does $2$ variable linear Diophantine equation in $NC$ imply $2$ dimensional shortest vector is in $NC$?
Consider the Linear Diophantine in known $a,b,c\in\mathbb Z$
$$ax+by=c.$$
Above can be solve by Extended Euclidean which is not in $NC$ as far as we know. It is clear if Extended Euclidean is in $NC$ ...
- 13.7k
0
votes
0
answers
148
views
On distribution of prime pairs coming from certain polynomials
Consider the polynomials
$$g(x)=(2x)^4+((2x)^2+1)^2$$
$$h(x)=(2x)^4+((2x)^2-1)^2.$$
If $k$ odd integers $x_1,\dots,x_k$ are uniformly randomly chosen in $(t,2t)$ and the polynomials are evaluated at ...
- 13.7k
13
votes
2
answers
711
views
How many players are needed so that two evenly matched teams can be picked?
We have a pool of $n$ players of a game, each player is assigned a "skill" which is an integer $1\leq s\leq 100$. We are now going to pick teams of $5$ players, where the team's skill is ...
- 315
0
votes
0
answers
318
views
Percent of rational coordinates that is a multiple of another point on the elliptic curve
Consider elliptic curves $E:= y^2=x^3+Ax+B $ (A, B are integers) which have points $P, Q$ with rational coordinates and satisfy $P=[n]Q, n>1$. Now consider the below problem:
Input: Rational ...
-2
votes
2
answers
149
views
Calculate the great common factor between $2^{2n+1}-1$ and $2^{4m+2}+1$ [closed]
How to calculate the great common factor between $2^{2n+1}-1$ and $2^{4m+2}+1$, where $n$ and $m$ are positive numbers.
We guess that: the great common factor is $1$.
- 577
1
vote
0
answers
128
views
Quadratic equations over Gaussian integers
Given an equation $x^2\equiv(a+ib)\bmod(c+id)$ where $a,b,c,d\in\mathbb Z$ holds, how to test if the equation has solutions and how to find the solutions in polynomial in $\log(|abcd|)$ time if $c+id$ ...
- 13.7k
0
votes
0
answers
69
views
Using coppersmith for bounded solution of a short linear Diophantine problem
I have a $3$-variable linear Diophantine equation
$$ax+by+cz=r$$ where $a,b,c,r\in\mathbb Z$ are known and can be as large in magnitude as needed and I know the equation has a solution $x,y,z\in\...
- 13.7k
84
votes
2
answers
6k
views
A little number theoretic game
I came up with this little two player game:
The players take turns naming a positive integer. When one player says the number n, the other player can only reply in two different ways: They can either ...
- 771
4
votes
4
answers
641
views
What or where is the series expansion of the function $\ln\bigl(\frac{\tan x}{x}-1\bigr)$ or $\ln(\tan x-x)$ around $x=0$?
It is known that
\begin{equation*}
\tan x=\sum_{k=1}^{\infty}\frac{2^{2k}\bigl(2^{2k}-1\bigr)}{(2k)!}|B_{2k}|x^{2k-1}, \quad |x|<\frac{\pi}{2}
\end{equation*}
and
\begin{equation*}
\ln\tan x=\ln x+\...
- 838
2
votes
0
answers
204
views
Modular inverse computation - avoiding Euclidean algorithm
Modular inverse is known to be computable by Extended Euclidean algorithm which is the reaping the rewards of computing the GCD of two numbers or proving two numbers are coprime.
If we already know ...
- 13.7k
1
vote
0
answers
114
views
Which real functions benefit from the Fundamental Theorem of Interval Analysis?
I'm reading Introduction to Interval Analysis, by Moore, Baker & Cloud and complementing it with Global Optimization using Interval Analysis, by Hansen & Walster.
Theorem 5.1 - Fundamental ...
5
votes
1
answer
301
views
Parity of number of solutions to Diophantine equations
By $MRDP$ resolution of Hilbert's tenth, we infer, counting number of solutions to Diophantine equations is undecidable.
Is parity of number of solutions to Diophantine equations undecidable?
- 13.7k
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
12
votes
1
answer
2k
views
Primality of a number of more than 50k digits
With modern tecnology is it possible to prove the primality of a number of more than 50k digits?
Obviously not a prime for which specific methods for testing primality are known like Mersenne primes.
1
vote
1
answer
121
views
Deduce kernel of isogeny from action on torsion points
I'm stuck with the following problem:
In Petit's work "Faster Algorithms for Isogeny Problems using Torsion Point Images", p. 8, he says that we can deduce $\ker \psi_{N_2}$ knowing the ...
- 63
3
votes
1
answer
252
views
What is meant by a meet-in-the-middle approach?
I'm studing C. Petit's work "Faster algorithms for isogeny problems using torsion point images" (link) and he talks about meet-in-the-middle approach/strategy for solve some isogenies ...
- 63