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
2
answers
477
views
Density stability; questions for those who like computer calculation
BACKGROUND: The question, which has its roots in a question asked on MO by O'Bryant, concerns the relative density of certain subsets, $B$, of ${\mathbb N}$ in congruence classes modulo a power of 2. ...
- 5,422
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
11
votes
1
answer
564
views
CM field to Torus to Abelian Variety?
Given a CM field we can use its maximal order (and a choice of CM type) to construct an abelian variety $\mathbb{C}^g/\Lambda$ with complex multiplication by the maximal order.
How do I (or where can ...
- 4,593
4
votes
1
answer
708
views
Calculating the constant in the Bateman-Horn-Stemmler conjecture
Bateman & Horn [1], building on Bateman & Stemmler [2], give a conjectured formula for the density of numbers that produce simultaneous primes in a number of fixed polynomials.
The constant ...
- 9,114
3
votes
2
answers
878
views
on the computation of decomposition groups
Let $L/K$ be a finite Galois extension of function fields, with Galois groups $G$. I want to look at the ramification of primes in the extension, i.e. to get $e_p$ and $f_p$ for a prime $p$ in the ...
- 249
0
votes
1
answer
342
views
Necessary/Sufficient condition/Algorithm that tells me a function field is a kummer extension
I start my question with an example. Suppose $F/K$ be the function field generated by $x^n - yx^{n-1} - 1 = 0$. It is not a cyclic over K(y), but if I set $t = yx^{n-1}$ then we have $K(x,t) \subset K(...
- 601
11
votes
0
answers
855
views
Points of bounded height in a number field
Let $K$ be a number field of absolute degree $d$, let $B$ be a positive real number, and write $S(K, B) = \{x \in K : H(x) \leq B\}$. Here $H$ is the absolute multiplicative height of an algebraic ...
- 1,199
0
votes
1
answer
180
views
Efficiency in deriving differences of divisor pairs
I have a computational problem where I need to derive the differences in divisor pairs in as few cpu cycles as possible.
In particular I am interested in divisors of numbers of the form $x^3+3*x^2*y+...
- 791
1
vote
1
answer
216
views
Counting modular squares in an interval
For an integer $m$, let $S^m_{x_0,x_1} = \{ t | x_0 ≤ t ≤ x_1 $ and $t$ is a square modulo $m \}$. Let $S^m_x$ = $S^m_{0,x}$.
Determining whether the sets $S^m_x$ are empty is easy (1 is always a ...
- 123
4
votes
0
answers
246
views
Algorithm/denominators of elements of a rational affine space
I hope it's not a trivial question... Suppose I have a finite dimensional vector space $V$ over $\mathbb{Q}$ with a distinguished basis (in my case it's the $k$th graded piece of the free associative ...
- 8,524
1
vote
0
answers
429
views
Witt rings and prime number generator?
Let $p$ be a fixed prime number. We define the ring of Witt vectors $W(R)$ for any commutative ring $R$ as follows:
For every ring morphism $R \rightarrow R'$ the induced morphism $W(R) \rightarrow ...
- 397
4
votes
1
answer
414
views
Computing places over x in F/K(x)
Let $F$ be a function field of "transcendental degree one" over its full constant field $K$. Let $x \in F \backslash K$. We know the divisor of $(x) = (x) - (1/x)$ in $K(x)$. Could you please give me ...
- 601
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
3
votes
0
answers
713
views
Tunnell's theorem
Is it possible in some way, to use Tunnells's theorem to determine how long it will take a computer, to determine whether a number n, is a possible area of a rational right triangle?
- 31
2
votes
0
answers
257
views
Efficient counting of Egyptian fractions with bounded denominators
I was amazed to discover that sequence http://oeis.org/A020473 in the OEIS has almost four hundred terms computed.
I wonder how one can get that far? E.g., how one can compute A020473(100)?
P.S. ...
- 34.4k
6
votes
1
answer
370
views
Speeding the quadratic sieve with an oracle
Suppose we have an odd composite $N$ and want to find numbers $a_1,\ldots,a_k$ such that each $a_i^2$, reduced mod $N$, is $b$-smooth. Of course we can use the quadratic sieve algorithm (minus the ...
- 9,114
4
votes
0
answers
369
views
Reducing factoring prime products to factoring integer products (in average-case)
My question is about the equivalence of the security of various candidate one-way functions that can be constructed based on the hardness of factoring. (This question has been asked also in the CS ...
- 41
5
votes
0
answers
292
views
Lower bound for p-adic distance between roots
Let $f$ be a formal power series with coefficients in the ring of integers of a finite extension of ${\mathbb Q}_p$. Is there a simple algorithm to compute a positive lower bound for $|\alpha - \beta|...
- 4,985
0
votes
0
answers
263
views
Computing the function field of a curve given as a subvariety of the Jacobian of its cover or merely the degree of the covering
I read following paragraph from:
G. Tamme, Teilkörper höheren Geschlechts eines algebraischen Funktionenkörpers, Arch. Math. 23 (1972), 257--259
Here $C$ is a curve of genus $\ge 2$ and $J$ is the ...
- 601
3
votes
2
answers
378
views
Upper bound on greatest prime of bad reduction for a plane curve
Background
We are given a curve with integer coefficients. I want to make a suggestion in another question (Computationally bounding a curve's genus from below?) into a deterministic algorithm ...
- 4,593
1
vote
0
answers
204
views
Which rational subfields are corresponding to the two dimensional subspaces of holomorphic differentials
I implemented the algorithm that Felipe Voloch's suggested in his reply to the question:
Subfields of a function field
the algorithm is here:
Subfields of a function field
I considered the ...
- 601
1
vote
0
answers
238
views
How to ask Magma to compute the induced morphisim on divisor group
Suppose Magma has computed homomorphism $h$ between function fields $F1 \to F2$. Then we have an induced homomorphism $h$ on the divisor group. Now my question is that if there's a better way to ...
- 601
1
vote
0
answers
123
views
What is the largest computed summatory liouville interval ?
I am interested to know the largest computed summatory liouville interval, an implementation of which is detailed in Section 4.1 of [1].
The wikipedia page [2] for the function charts summatory ...
- 11
4
votes
0
answers
159
views
Range of the least witness function
Let W(n) be a function from the positive odd composite numbers to the least positive b such that n is not a b-strong pseudoprime. W(n) exists for all numbers in its domain and its range is unbounded. ...
- 9,114
5
votes
0
answers
228
views
Example of level one cuspidal Hecke Algebra T_k^0 such that p divides its index in its normalization, and p≥k-1?
The question is strongly focused on computations concerning modular forms and Hecke algebras. It is already in the title, but I will repeat it, adding a few details.
Let $S_k$ be the complex vector ...
- 2,406
1
vote
0
answers
108
views
Why do subspaces of the space of Global holomorphic differentials of a function field correspond to its subfields
I'm asking this question as a follow up to the Felipe Voloch's answer to this question:
Subfields of a function field
which you can read it here:
Subfields of a function field
(I just didn't have ...
- 601
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 ...
