# Tagged Questions

**3**

votes

**0**answers

122 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 ...

**2**

votes

**1**answer

101 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 ...

**0**

votes

**1**answer

100 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

**1**answer

184 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

**1**answer

231 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 ...

**3**

votes

**2**answers

192 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

**1**answer

292 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

**1**answer

346 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

**1**answer

197 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

**0**answers

310 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 ...

**4**

votes

**2**answers

392 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

**1**answer

178 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

**0**answers

218 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

**2**answers

187 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 ...

**12**

votes

**3**answers

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

**3**answers

584 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

**3**answers

374 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

**1**answer

339 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

**1**answer

165 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

**2**answers

498 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 ...

**8**

votes

**1**answer

269 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 ...

**11**

votes

**2**answers

673 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 ...

**0**

votes

**2**answers

977 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 ...

**1**

vote

**0**answers

163 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. ...

**9**

votes

**3**answers

898 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. ...

**15**

votes

**2**answers

943 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 ...

**11**

votes

**2**answers

647 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$ ...

**4**

votes

**2**answers

878 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 ...

**1**

vote

**0**answers

335 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 ...

**7**

votes

**3**answers

770 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 ...

**4**

votes

**0**answers

193 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 ...

**4**

votes

**0**answers

129 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. ...

**0**

votes

**0**answers

173 views

### Number of biquadrates mod n

Is there an explicit formula for the number of fourth powers mod n?
Finch & Sebah [1] give theorems, partially folklore, for squares and cubes mod n, but I don't know of a similar formula for ...

**7**

votes

**1**answer

613 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 ...

**2**

votes

**0**answers

268 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 ...

**0**

votes

**0**answers

243 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 ...

**3**

votes

**1**answer

364 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 ...

**9**

votes

**0**answers

496 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 ...

**5**

votes

**1**answer

418 views

### Effective bounds on Euler's totient

Quick question: It's known that
$$\limsup\frac{n}{\varphi(n)\log\log n}=e^\gamma$$
but are there known C and N such that
$$\varphi(n)>\frac{Cn}{e^\gamma\log\log n}$$
for all $n>N$?
Failing ...

**8**

votes

**2**answers

405 views

### Efficient computation of the least fraction with square denominator greater than the square root of 2.

The least rational number greater than $\sqrt{2}$ that can be written as a ratio of integers $x/y$ with $y\le10^{100}$ can be found in a moment using a little Python program. Can anyone write a ...

**16**

votes

**2**answers

1k views

### Computing (on a computer) the first few (non-trivial) zeros of the zeta function of a number field.

Let $M$ be the splitting field of
x^8 + 3*x^7 + 13*x^6 + 17*x^5 + 45*x^4 + 37*x^3 + 11*x^2 + 112*x + 108
over the rationals. If I've understood some tables ...

**1**

vote

**1**answer

3k views

### What is the longest known sequence of consecutive zeros in Pi? [closed]

Inspired by this question, I would like to know what is the longest known sequence of consecutive zeros in Pi (in base 10).
So far the longest I have found is the sequence of 8 zero's occurring in ...

**0**

votes

**1**answer

277 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 ...

**1**

vote

**1**answer

321 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 ...

**8**

votes

**3**answers

1k views

### Most efficient checking algorithm for Pell's Equation

What is the most computationally efficient way to check, given $x,y,D$ that they satisfy Pell's equation (positive or negative) ($x^2-Dy^2=1$)? (Obviously the question is concerned with very large ...

**37**

votes

**2**answers

5k views

### Walsh Fourier Transform of the Möbius function

This question is related to this previous question where I asked about ordinary Fourier coefficients.
Special case: is Möbius nearly Orthogonal to Morse
!
Harold Calvin Marston Morse (24 March ...

**11**

votes

**1**answer

498 views

### How many LLL reduced bases are there?

For a given $n$-dimensional lattice embedded inside $\mathbb R^n$ along with a given inner product, how many distinct LLL-reduced bases are there?
In this question, a lattice is the set of all ...

**13**

votes

**2**answers

889 views

### Subfields of a function field

Is there an algorithm for generating (some or all) subfields of a certain genus of a given function field (even a random one,I mean for example generating a random elliptic subfield of a certain given ...

**6**

votes

**2**answers

914 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 ...

**18**

votes

**1**answer

554 views

### How to explicitly compute lifting of points from an elliptic curve to a modular curve?

Say $E$ is an elliptic curve over the rationals, of conductor $N$. There's a covering of $E$ by the modular curve $X_0(N)$, and if you rig it right then you can define this map over $\mathbf{Q}$: ...