33
votes

Accepted

### Does any cubic polynomial become reducible through composition with some quadratic?

You should refer to Lemma 10 (page-233) in this paper by Schinzel where he proves that for any polynomial $F(x)$ of degree $d$ we have a polynomial $G(x)$ of degree $d-1$ such that their ...

- 878

33
votes

Accepted

### Non-trivial solutions for $-(c^2-d^2)(a^2-b^2)=2(ad-bc)(bd+ac)$?

There is no such solution. Let
$$
Q(a,b,c,d) = 2(ad-bc)(bd+ac) + (a^2-b^2)(c^2-d^2)
$$
be the difference between the two sides of the equation,
so we seek to solve $Q(a,b,c,d) = 0$. This is a ...

- 72.6k

21
votes

### What computer program for automorphic forms

The only CAS's that have built-in support for modular and automorphic forms, as far as I know, are Sage and Magma. [Edit: I had forgotten Pari/GP, which will introduce substantial modular forms ...

- 32.6k

20
votes

Accepted

### Possible contemporary improvement to bounded gaps between primes?

I think that there is indeed some possibility to lower the bound, and this is something I've looked at seriously a few times. I spent a semester (in 2019) with the Computational Number Theory Group ...

- 15.4k

20
votes

Accepted

### Is there a way to specify a special kind of reciprocals of natural numbers?

This is a textbook example of a question for which one should turn to the OEIS for assistance. The first few elements of this set are
$$ 7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, ...

- 92.8k

18
votes

### Sum of squares and divisibility

This is not a complete answer, but just a way to transform the problem into one that can be attacked by brute force in some known way.
Write $d_i^2=N/n_i$. Then your relation becomes $$\frac{1}{n_1}+ \...

- 62.5k

17
votes

Accepted

### Question on the 50th (known) Mersenne prime number

As Jan Grabowski notes, all the primes that you mention have been discovered by GIMPS. GIMPS draws a distinction between testing and double-checking. When a Lucas–Lehmer test is performed on a ...

- 67.1k

16
votes

Accepted

### simple conjecture on palindromes in base 10

Using
$$\frac{10^c-1}{9}=\sum_{m=0}^{c-1} 10^m,$$
the product in question equals
$$\sum_{n=0}^{2a+2b+c-1}r(n)10^n,$$
where $r(n)$ is the number of times $n$ occurs among the numbers (counted with ...

- 87k

16
votes

Accepted

### Representing field elements in a computer

You are looking at a computable field (if your focus is on the field), or a computable presentation of a field (if your focus is on the details of how elements and operations are coded). These objects ...

- 3,401

16
votes

### Extension of Dickson's theorem on integers of the form $a^2+b^2+2c^2$

Answer to Question 1. Yes, $E(\mathbb{Z})=F$.
The inclusion $F\subseteq E(\mathbb{Z})$ follows from $E\subseteq E(\mathbb{Z})$ and Dickson's result $E=F$. It remains to show $E(\mathbb{Z})\subseteq F$...

- 2,519

15
votes

Accepted

### Computing an eigencuspform in $S_2(\Gamma_0(1776))$

I did the computation in Sage, and there is no such form $f$. There are 21 Galois orbits of newforms of level $\Gamma_0(1776)$ and trivial character, of which the largest has size 3, and none of the ...

- 32.6k

15
votes

Accepted

### Goldbach conjecture and other problems in additive combinatorics

It seems what you are asking is "If we have a precise asymptotic for the number of elements of a set, can we solve binary additive problems involving that set?"
The answer in general seems ...

- 11.2k

15
votes

Accepted

### Expressing primes $p\equiv 1 \pmod 3$ in the form $p = x^2 + xy + y^2$

This is an elaboration of the answer that Noam Elkies provided in the comments.
Suppose that $p=x^2 + xy + y^2$. Then note that $x$ and $y$ are small relative to $p$ (at most half as many digits). ...

Community wiki

14
votes

14
votes

### In which cyclic cubic number fields does there exist this type of unit?

The answer to question 1 is yes.
Pick any field element $x_1$ outside the rationals. Let $x_2$ and $x_3$ be its conjugates under the Galois group. Then the cross ratio $$w=\frac{(x_1-1)(x_2-x_3)}{(...

- 2,177

14
votes

### Fermat's last theorem $\pm1$

[EDITED] It is likely that there are no solutions at all for $n \ge 4$. For $n \ge 5$ a solution would be a counterexample to the Lander, Parkin, and Selfridge conjecture. The best FLT "near ...

- 51.8k

13
votes

Accepted

### An efficient isomorphism between finite fields

Google provides an answer to this question. The first deterministic polynomial time algorithm for this is due to H. W. Lenstra, Jr., in his paper "Finding isomorphisms between finite fields" (...

- 6,269

13
votes

Accepted

### Computational complexity of finding the smallest number with n factors

The problem asks for the least number $N$ such that the number of divisors of $N$ is at least $n+2$. Since all numbers below $N$ must have fewer divisors, clearly $d(N) > d(m)$ for all $1\le m <...

- 42.6k

13
votes

### Twin primes conjecture and extrapolation method

This is just to present a numerical curiosity. I suspect that it is coincidental, but I feel compelled to share it in case anyone wants to look further.
First some disclaimers: Consider a random walk ...

- 29.6k

12
votes

### Explicit formula for elementary symmetric sum

More specifically, $e_k(j)=c(j+1,j+1-k)$, where $c(j+1,j+1-k)$ is a signless Stirling number of the first kind. For a discussion of this polynomial see http://math.mit.edu/~rstan/pubs/pubfiles/29.pdf. ...

- 45.6k

12
votes

### How close can powers of coprime integers get?

You can get a conjectural lower bound for $|a^x-b^y|$ using the $ABC$-conjecture. I'll do the case $a^x > b^y$ for simplicity. Taking $A=a^x$, $B=-b^y$, and $C=a^x-b^y$, we get for every $\epsilon &...

- 42.7k

12
votes

Accepted

### GRH and the rank of elliptic curves

Computation of ranks of elliptic curves relies on descent. The first step of descent is the computation of a finite Selmer group, which in turn uses the computation of the class group of a potentially ...

- 4,194

12
votes

### Do consecutive integers have a big prime factor?

Shorey and Tijdeman, On the greatest prime factors of polynomials at integer points, Compositio Mathematica, tome 33, no 2 (1976), p. 187-195
http://www.numdam.org/item?id=CM_1976__33_2_187_0 note ...

- 36.5k

12
votes

### About the complexity of some operation involving integers

There is a simple algorithm because the minimal path from $A$ to $B$ using these operations must have a very constrained form.
First, an optimal sequence of $x+1$ and $x-1$ operations from $a$ to $b$ ...

- 40.3k

11
votes

Accepted

### Are there highly composite prime gaps?

Assuming the prime tuples conjecture, all of these questions have affirmative answers. For instance, one can use the Chinese remainder theorem to find $a,b$ such that the tuple
$$ an+b, \frac{an+b+1}{...

- 92.8k

10
votes

### Computing millions of coefficients of non self-dual modular forms

One shortcut you could use for computing the level 17 form you link to would be the following. There are exactly 8 Eisenstein series of weight 1 for $\Gamma_1(17)$ and they are all given by completely ...

- 32.6k

10
votes

### Is there an efficient algorithm for finding a square root modulo a prime power?

An explicit formula is given in Tonelli's 1891 note referred to in the Wikipedia entry on the Tonelli-Shanks algorithm: Given a prime $p>2$ and a quadratic residue $a \bmod p$, let $x$ be a square ...

10
votes

### existence of an elliptic curves with given number of points over finite field

Deuring proved that for every $a, |a| < 2\sqrt{p}$, there exists an elliptic curve with $p+1-a$ points over $\mathbb{F}_p$.
M Deuring, Die Typen der Multiplikatorenringe elliptischer ...

- 29.6k

10
votes

### Explicit formula for elementary symmetric sum

Yes. What you ask about are Stirling numbers of the first kind $s(j,j-k)$. Formula (21) http://mathworld.wolfram.com/StirlingNumberoftheFirstKind.html is an explicit expression for fixed $k$.

- 90.4k

10
votes

### Do these rational sequences always reach an integer?

I want to leave a few elementary comments, maybe they will be helpful.
The question asks about recurrence relation
$$
u_{n+1}= \lfloor u_n \rfloor (u_n − \lfloor u_n \rfloor + 1)
$$
Suppose you write ...

- 817

Only top scored, non community-wiki answers of a minimum length are eligible

#### Related Tags

computational-number-theory × 385nt.number-theory × 276

prime-numbers × 60

computational-complexity × 55

algorithms × 53

analytic-number-theory × 51

algebraic-number-theory × 47

reference-request × 24

co.combinatorics × 24

polynomials × 21

modular-forms × 19

diophantine-equations × 18

computer-algebra × 16

ag.algebraic-geometry × 14

elliptic-curves × 14

factorization × 13

ac.commutative-algebra × 9

cryptography × 9

linear-algebra × 8

arithmetic-geometry × 8

na.numerical-analysis × 8

computer-science × 8

additive-combinatorics × 7

gr.group-theory × 6

ds.dynamical-systems × 6