The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
45 views

Runge-Kutta convergence [on hold]

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 ...
0
votes
0answers
51 views

lattice basis reduction of the orbit of a rational vector on the torus

LEt $v=(p_1/q,...,p_n/q)$ be a vector of the torus $\mathbb{T}^n$, such that for any $i$, $p_i$ and $q$ are relatively prime. Let $L= \{ kv \mod \mathbb{T}^n , k=0,...,q-1 \}$. What is the lattice ...
5
votes
1answer
282 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 ...
4
votes
0answers
265 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 ...
9
votes
3answers
351 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 ...
2
votes
0answers
109 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 ...
2
votes
0answers
99 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 ...
1
vote
1answer
219 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 ...
1
vote
1answer
223 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 ...
1
vote
0answers
50 views

How can I interpolate between these sets of algebraic integers?

Consider the set $S_d(m)$ of algebraic integers whose minimal polynomials are of degree $\leq d$ and have constant and leading coefficients $+1$, and all other coefficients chosen from the set ...
4
votes
0answers
174 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 ...
7
votes
0answers
234 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$. ...
1
vote
1answer
153 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 ...
2
votes
1answer
214 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 ...
3
votes
0answers
172 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})$. ...
1
vote
0answers
178 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, ..., ...
2
votes
3answers
227 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
votes
0answers
147 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 ...
6
votes
0answers
415 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 ...
2
votes
1answer
108 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
2answers
304 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 ...
0
votes
1answer
105 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 ...
3
votes
1answer
204 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.
1
vote
1answer
264 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 ...
1
vote
0answers
84 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 ...
4
votes
2answers
281 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 ...
1
vote
1answer
306 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, ...
2
votes
1answer
360 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 ...
0
votes
1answer
198 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 ...
2
votes
2answers
264 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 ...
6
votes
3answers
816 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
0answers
346 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 ...
0
votes
0answers
173 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 ...
4
votes
2answers
416 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?
3
votes
1answer
199 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) ...
7
votes
0answers
232 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? ...
1
vote
2answers
202 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 ...
0
votes
2answers
494 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
1answer
851 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, ...
3
votes
0answers
257 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 ...
12
votes
3answers
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 ...
8
votes
3answers
794 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 ...
3
votes
3answers
492 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 ...
6
votes
1answer
381 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 ...
1
vote
1answer
181 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 ...
2
votes
2answers
621 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 ...
4
votes
1answer
235 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 ...
0
votes
1answer
156 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 ...
5
votes
2answers
560 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 ...
8
votes
1answer
280 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 ...