Questions tagged [computational-number-theory]
Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.
476 questions
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 ...
CommunityBot
- 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.
15
votes
2
answers
1k
views
Sum of $\sum_{k=1}^nd(k^2)$
There is a literature dealing with
$$
\sum_{k\le x}d(f(k))
$$
where $f$ is an irreducible polynomial and $d(n)$ is the number of divisors of $n$. Erdos 1952 shows that the sum $\asymp x\log x,$ which ...
- 12.3k
26
votes
3
answers
16k
views
How good is Kamenetsky's formula for the number of digits in n-factorial?
In Number of digits in n!, now closed, there was a mention of Dmitry Kamenetsky's formula, $[\bigl(\log(2\pi n)/2+n(\log n-\log e)\bigr)/\log 10]+1$, for the number of decimal digits in $n$-factorial. ...
CommunityBot
- 1
5
votes
4
answers
866
views
Reconstructing a fraction from its first digits
It is not difficult to see that any reduced fraction $\frac{p}{q}$
where $0 < p < q $ and both $p$ and $q$ have at most $N$
digits (where $N$ is a fixed integer) can be reconstructed
from its ...
CommunityBot
- 1
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 ...
CommunityBot
- 1
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 ...
- 13.5k
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
15
votes
3
answers
3k
views
Finding zeroes of classical modular forms
There are several papers which compute zeroes of modular forms for genus 0 congruence subgroups, such as "Zeros of some level 2 Eisenstein series" by Garthwaite et al published in Proc AMS and work of ...
- 11.2k
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?
- 11.4k
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, ...
CommunityBot
- 1
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 ...
CommunityBot
- 1
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)...
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
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 ...
CommunityBot
- 1
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
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 ...
CommunityBot
- 1
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]...
- 743
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, ...
- 5,502
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)$ ...
- 13.9k
3
votes
1
answer
426
views
Optimize / simple Set Covering Problem
Let $k,m\in\mathbb{N}$ be given. Let $M:=\{0,... , m-1\}$. How to find a subset $T\subset M$, $|T|=k$ such that $|T+T|$ is maximal, where $T+T=\{ (a+b)\mathbin\%m \mid a\in T,b\in T \}$ (“%” means ...
CommunityBot
- 1
15
votes
2
answers
1k
views
Saying things rapidly about integer factorisations
Let $N$ be a positive integer. Thanks to the Miller-Rabin test and the work of Agrawal, Kayal and Saxena, these days people have much much faster algorithms for testing whether $N$ is prime or ...
- 2,913
8
votes
3
answers
1k
views
Effective detection of CM modular forms
Say $f$ is a newform of weight $k$ and level $\Gamma_1(N)$. $f$ is called CM if, for example, there is an imaginary quadratic field $K$ such that for all $p\nmid N$ which are inert in $K$, the $p$th ...
CommunityBot
- 1
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
11
votes
1
answer
2k
views
Integer values of a rational function
Suppose we are given a rational function with numerator and denominator being polynomials with integer coefficients. Is there an efficient algorithm for finding all integers arguments at which the ...
CommunityBot
- 1
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.3k
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
12
votes
1
answer
869
views
Analytic lower bounds on the first sign change of pi(x) - li(x)?
There have been many results on the first sign change of $\pi(x)-{\mathrm{li}}(x)$: among others, Lehman, te Riele, Bays & Hudson, Demichael, Chao & Plymen, and most recently Saouter & ...
- 12.3k
3
votes
2
answers
2k
views
Integer partition and sum of squares
Hello,
The question below might be well known, and using different words (I made these up, I'm not a number theorist or specialist in combinatorics)
For all integers $n\geq 2$ denote by $\mathcal{P}...
- 2,829
4
votes
1
answer
389
views
Most orthogonal lattice basis
Let $n \in \mathbf{N}$ be a natural number and $v_1,\cdots,v_n$ a set of basis vectors in $\mathbb{R}^n$. How does one find the matrix $g \in \mathbf{GL}_n(\mathbb{Z})$ orthogonalizing these best ...
CommunityBot
- 1
5
votes
2
answers
851
views
12 descent scripts for pari/gp
I'm looking around for scripts to facilitate 12 descent on Mordell curves, preferably in Pari/gp.
I understand that Magma implements this feature, but unfortunately this software isn't available to ...
11
votes
1
answer
360
views
Does this notion of pseudoprime relative to a matrix appear in the literature?
Let $M$ be a square matrix with integer entries. Then Fermat's little theorem for matrices holds:
$$\text{tr}(M^p) \equiv \text{tr}(M) \bmod p.$$
This follows by an examination of the action of the ...
- 386
68
votes
7
answers
5k
views
Open project: Let's compute the Fourier expansion of a non-solvable algebraic Maass form.
OK so let's see if I can use MO to explicitly compute an example of something, by getting other people to join in. Sort of "one level up"---often people answer questions here but I'm going to see if I ...
CommunityBot
- 1
0
votes
2
answers
3k
views
Fibonacci Numbers Modulo m [closed]
In the paper "Fibonacci Series Modulo m" by D.D. Wall (found here), there is a table in the Appendix listing values for the function $k(p)$. This function is defined as the period of the Fibonacci ...
- 12.1k
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 ...
- 39.9k
11
votes
3
answers
2k
views
Mertens' function in time $O(\sqrt x)$
This MathOverflow question seems to indicate that the state of the art in computing
$$
M(x)=\sum_{n\le x}\mu(n)
$$
takes time $\Theta(n^{2/3}(\log\log n)^{1/3}),$ which matches my understanding. ...
CommunityBot
- 1
2
votes
0
answers
256
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. ...
CommunityBot
- 1
11
votes
2
answers
754
views
Interesting result on the Euler-Maschroni constant - what is the background?
Today I entered the following expression in maple:
$$a_i = H_{10^i} - ln(10^i) - \gamma$$
Here $H_j$ equals $\sum_{k=1}^{j} 1/k$ and $\gamma$ is the Euler-Mascheroni constant.
When I computed $a_n$ ...
- 5,342
9
votes
2
answers
807
views
Complexity of Membership-Testing for finite abelian groups
Consider the following abelian-subgroup membership-testing problem.
Inputs:
A finite abelian group $G=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}$ with arbitrary-...
CommunityBot
- 1
6
votes
2
answers
2k
views
Computing the fixed field of an automorphism of a function field
Let say we have a function field $k(x,y)$ defined by $f(x,y)$ over $k$, with $\sigma \in Aut(k(x,y)/k)$ and. Suppose, I'm not that out of luck, so that either of $\prod \sigma^i(x)$ or $\sum \sigma^i(...
- 601
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. ...
CommunityBot
- 1
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 ...
CommunityBot
- 1
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 ...
- 50.6k
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
7
votes
2
answers
1k
views
Recovering n from sigma(n)/n
For any positive integer $n$, we define
$$\sigma(n) := \sum_{d \mid n} d,$$
and
$$\delta(n) := \frac{\sigma(n)}{n} = \sum_{d \mid n} \frac{1}{d}.$$
Is there an (efficient) way to determine $\delta^{-1}...
5
votes
0
answers
290
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
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 ...
CommunityBot
- 1
8
votes
1
answer
716
views
Finding colinear points in F_q^n
Forgive me if this is well known, it's not really my field, but it's a problem I've run across and thought about a bit.
Let $\mathbb{F}_q$ be a finite field with $q$ elements, let $n\ge2$, and let $A,...
- 18.8k
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 ...
CommunityBot
- 1
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