All Questions
Tagged with computational-number-theory algebraic-number-theory
63 questions
1
vote
1
answer
240
views
The equation $ax^2 +by^2 =1 \mod P$ in cyclotomic field
Let $L$ be a cyclotomic field, and $P$ a prime ideal of $\mathcal{O}_L$.
is there any symbol for the equation $ax^2 + by^2 =1 \mod P$ and if so, is it computable in polynomial time?
if $a$ is ...
- 133
3
votes
1
answer
203
views
Chowla's theorem on class number of real quadratic field
Let $p\equiv1\bmod 4$ be a prime number and $h$
the class number of real quadratic field $\mathbb Q(\sqrt{p})$, $\epsilon=\frac{t+u\sqrt{p}}{2}$ its fundamental unit. In this paper https://www.pnas....
- 287
1
vote
0
answers
62
views
A conjecture on members of Lucas sequences not being pseudoprimes
Following conjecture on an infinite set of numbers satisfying the PSW-conjecture might be of academic interest in the understanding thereof.
Would you have any pointers on how to prove or disprove ...
2
votes
1
answer
157
views
$f(x)\bmod p$ and decomposition of prime ideals
While reading Serre's beautiful book Lectures on $N_X(p)$, I thought of a related question.
Let $f(x)\in \mathbb{Z}[x]$ be a monic irreducible polynomial with integer coefficients. Let $K$ be the ...
- 709
14
votes
2
answers
683
views
Can four integer numbers $x$, $y$, $x-y$, $x+y$ be powerful numbers where $\gcd(x,y)=1$?
Can four integer numbers $x$, $y$, $x-y$, $x+y$ be powerful numbers where $\gcd(x,y)=1$ ?
- 1,776
2
votes
0
answers
107
views
Record for determining complete list of imaginary quadratic fields with small class number
In 2003, Mark Watkins (Class numbers of imaginary quadratic fields) determined all imaginary quadratic fields having class number at most 100.
Has this list been improved? That is, what is the largest ...
- 26.9k
2
votes
0
answers
119
views
gcrd and associates of an element of the quaternion algebra over a totally real number field $K$
Let $K$ be a totally real number field of class number 1, and $Q$ the quaternion algebra over the ring of integers of $K$ with basis
$\{1,i,j,k\}$ such that $i^2 = j^2 = k^2 = -1$ and $ij = -ji, ik = ...
- 133
5
votes
0
answers
187
views
Is there an effective way to compute the square root of an algebraic number?
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,087
1
vote
1
answer
73
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 ...
- 411
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,087
4
votes
1
answer
222
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 ...
- 43
0
votes
1
answer
126
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
64
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 ...
1
vote
0
answers
64
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
-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
2
votes
0
answers
93
views
Integers solutions of products of truncated Riemann zeta functions
Let $n \in \mathbb{N}$ be a positive integer.
It is possible to prove that the equation $F_1(n)=m$ where $m \in \mathbb{Z}$ and
$$
F_1(n)=(1+2+\ldots+n)\cdot\left(\frac{1}{1}+\frac{1}{2}+\dots+\frac{1}...
- 1,343
5
votes
1
answer
234
views
What are the solutions in numbers of $xyz \mid x^n + y^n + z^n$, $x,y,z$ globally coprime
What are globally coprime integers $x,y,z\in \mathbb Z^*$ such that $xyz$ divide $x^n + y^n + z^n$?
I have no other motivation for that problem but its inherent beauty and interest.
Note that it can ...
- 687
1
vote
0
answers
50
views
Algorithm to compute S-units in imaginary quadratic number field
What efficient algorithms are there to compute the $S$-units of a given imaginary quadratic field $K$, where $S$ is a finite set of non-archimedean primes?
Computing $S$-units are implemented in ...
- 577
7
votes
1
answer
622
views
Algorithm for computing whether a cubic field is monogenic?
I am interested in existing algorithms to compute whether a given non-cyclic, non-pure cubic extension $K/\mathbb{Q}$ is monogenic or not, and if so, to give me a defining polynomial for the integral ...
- 565
4
votes
0
answers
102
views
Reconstructing coefficients of an elliptic curve L-series from the modular form divisor
Let $E$ be an unknown elliptic curve over $\mathbb{Q}$.
Let $L(E, s) = \sum_{n=1}^{\infty} \frac{a_n}{n^s}$ be the L-function of $E$ and write $f(q) = \sum_{n=1}^{\infty} a_n q^n$.
I'm in a setting ...
- 5,637
9
votes
1
answer
737
views
Square root in number field
I'm trying implement an algorithm that, for an element $b$ of a number field $\mathbb{Q}(\alpha)$, if it is a square in $\mathbb{Q}(\alpha)$ (i.e., $\exists x\in\mathbb{Q}(\alpha):x^2=b$), computes ...
- 153
0
votes
1
answer
63
views
Changing base field for sum of polynomials
Let $L/\mathbb{Q}$ be a finite extension and $f_{1},\dotsc,f_{n}\in L[x_{1},\dotsc,x_{k}]$ be degree $d$ homogeneous polynomials. Is there a way to find homogenous degree $d’$ polynomials $g_{1},\...
- 3
2
votes
0
answers
300
views
How soon can we represent a number as the sum of two primes?
Posting in MO since it was unanswered in MSE.
Goldbach's conjecture says that every even number can be represented as the sum of two primes. But how soon can we find such a representation. Taking $20 =...
- 5,470
1
vote
0
answers
84
views
How common are semiprimes with equally bitsized factors among semiprimes with equal bitsize?
I am curious about the following after having looked at the paper "Almost primes in almost all short intervals", theorem 3 says:
Almost all intervals $[x, x + \log^{3.51}{(x)}]$ with $x ≤ X$...
- 11
2
votes
1
answer
514
views
Eisenstein polynomial of totally ramified extension over $p$-adic field
Let $p\geq 3$ be a prime number, $K$ be a finite extension of $\mathbb{Q}_p$ with no non-trivial unramified subextension, $f(x)$ be an irreducible monic polynomial in $\mathcal{O}_K[x]$, making $L=K[x]...
- 549
8
votes
0
answers
245
views
Hilbert 10th problem for genus 2 equations
Hilbert 10th problem, while undecidable in general, remains open for 2-variable equations: we do not know if there is an algorithm that, for polynomial $P(x,y)$ with integer coefficients, decides ...
- 7,182
3
votes
1
answer
116
views
Can we construct composite Fermat pseudoprimes to integral algebraic bases?
Let $0\neq \beta\in\overline{\mathbb{Z}}$ and let $n$ be a positive integer coprime to $N_{\mathbb{Q}(\beta)/\mathbb{Q}}(\beta)$. Say that $n$ is a Fermat pseudoprime to base $\beta$ if
$$\beta^{n^{[\...
- 458
1
vote
3
answers
302
views
How do I find abelian cubic extension over $\mathbb{Q}$ with class number more than 1?
I am trying to see them as subfield $\mathbb{Q}(\zeta_n).$ I feel it is a tiring job by using SageMath. Moreover, I am ending up with the abelian cubic field with the class number $1.$
I appreciate ...
- 743
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
3
votes
1
answer
270
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
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
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
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
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
3
votes
1
answer
227
views
How can we justify the use of Example 5,4 (of Cohen, Lenstra) assuming their heuristics
In these days, I'm studying Cohen-Lenstra heuristics to understand the paper of Rene Schoof "Class Numbers of Real Cyclotomic Fields of Prime Conductor".
On page 932 of Schoof's paper, there is a ...
- 1,013
2
votes
0
answers
137
views
Compare my software's representation of exponential numbers and 0?
Suppose I have a real number
$$
x=\sum_{i=1}^n a_i e^{\lambda_i}
$$
where $a_i,\lambda_i$s are complex algebraic numbers.
Is there an algorithm to determine whether it is greater than 0 or less than ...
- 1,503
5
votes
2
answers
932
views
How can I find explicit examples of maximal orders of quaternion algebras that are not isomorphic?
I know that there exist algorithms that will construct maximal orders of a quaternion algebra over, say, $\mathbb{Q}$. However, the implemented algorithms that I know of require that you input an ...
3
votes
1
answer
293
views
Number of lattice points on spheres with center not at the origin
Let $k\ge1$. It is known that the number of lattice points on the $k$-sphere $S^k(0)$ (center at the origin, radius $R$), namely the size of $\mathbb{Z}^{k+1}\cap S^k(0)$, is bounded by $R^{k-1+\...
- 187
5
votes
0
answers
195
views
Is there some computational evidence of the $pq$ analog of Serre's conjecture?
The $pq$ analog of Serre's conjecture (see "Mod pq Galois representations and Serre's Conjecture"- Khare, Kiming) states that if $\bar{\rho}_1:G_{\mathbb{Q}}\rightarrow \text{GL}_2(\mathbb{F}_p)$ is a ...
user130124
0
votes
1
answer
809
views
Conjecture that relates matrix systems with some specific functions as solution sets
what is written below is a conjecture that I posed , and I ask for a proof or a disproof of it .I have checked the conjecture from $n$=$1$ up to $n$=$10$ using Matlab, and all results were in ...
18
votes
4
answers
1k
views
In which cyclic cubic number fields does there exist this type of unit?
Let $K$ be a cyclic cubic number field with conductor $f$ and ring of integers $\mathcal{O}_K$.
Define $K$ to be blue if and only if $$\operatorname{Norm}_{K/\mathbb{Q}}(w) = \operatorname{Norm}_{K/...
0
votes
1
answer
159
views
Parity and number of squares taken by polynomials in a range?
I have a polynomial $f(x)=a^2x^2+bx+c\in\mathbb Z[x]$ with $f(x)$ not a constant times a square and $abc\neq0$ and I want to know how many $x$ between $-a$ and $a$ the polynomial is a perfect square. ...
- 13.9k
6
votes
2
answers
323
views
Computing the relative class group (with Galois action) of relatively large cyclotomic groups
For a cyclotomic field $K = \mathbb Q(\zeta_n)$, let $K^+$ be its maximal totally real subfield. We know that $H^+ = Cl(K^+)$ injects into $H = Cl(K)$. I am interested in computing the group $H/H^+$ ...
- 7,746
3
votes
1
answer
238
views
Norm of a Vector in a Number Field (or Order in a Number Field)
I am looking for a measurement, which gives a length of a vector in a number Field? Is there any way or definition for that.
For the Maximal order, What if, I tried to define a map from Maximal order ...
- 149
1
vote
0
answers
133
views
Finding Generators of an Ideal Over Number Field? [closed]
Is there any way or algorithm to find generators of an ideal over number field? (A algorithm that can be implemented and not expensive)
- 149
-1
votes
1
answer
177
views
Solving quaternary quadratic forms modulo $q$ efficiently
Given a quaternary quadratic equation of form $$Q(a,b,c,d)=m$$ in $\Bbb Z[a,b,c,d]$ with coefficient sizes and $|m|$ bounded in magnitude by $B\in\Bbb N$ where $m\neq0$ if we are looking for solutions ...
- 13.9k
3
votes
0
answers
164
views
Explicit roots in algebraic extention of Q with roots
Denis Bouhineau in "Solving Geometrical Constraint System Using CLP Based on Linear Constraint Solver" gave a method to find explicit square root in algebraic extention of Q with square roots. For ...
2
votes
0
answers
57
views
fast computation of cyclic totally real number fields of given degree and conductor
Let $n$ be an odd prime and $l$ also a prime s.t. $l\equiv1 \bmod n$. I want a fast way to compute the $n^{th}$ degree subextension of the $l^{th}$ cyclotomic field. I need to compute lots of these in ...
1
vote
1
answer
256
views
Lattice Sieving
What are some good references for Lattice Sieving in Number Field Sieve? Could someone suggest some research papers in this area?(Theoretical and Computational Perspective)
- 63