21

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 functionality as of version 2.10 which is currently in alpha testing; see Aurel's comment below]. Both Sage and Magma offer roughly comparable functionality. In Sage ...

answered Apr 27 '18 at 11:13

David Loeffler

28.5k33 gold badges6464 silver badges148148 bronze badges

18

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 here at BYU trying to do it, without success. Let me outline some of the difficulties we found.
Issue 1. The main technique used in establishing the current ...

16

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 Mersenne number and delivers a verdict that the number is prime, the computation is immediately verified. Only after the verification checks out is it ...

answered Jan 16 '18 at 14:49

Timothy Chow

56.4k1919 gold badges255255 silver badges430430 bronze badges

16

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 multiplicity)
$$\begin{matrix}
m+2a+2b,&m+2a+b,&m+2a,\\
m+a+2b,&m+a+b,&m+a,\\
m+2b,&m+b,&m,\\
\end{matrix}$$
for some $m\in\{0,1,\dots,c-1\}$...

16

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 are studied in computable structure theory.

16

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$. Pick $n\in E(\mathbb{Z})$. By definition there exist $u,v\in\mathbb{Z}^3$ such that $\lVert u\rVert=\lVert v\rVert$ and $n=\lVert u\rVert^2+\lvert u\cdot v\...

nt.number-theory co.combinatorics additive-combinatorics computational-number-theory sums-of-squares

15

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 reductions modulo any of the primes above 7 in the coefficient fields is congruent to the form associated to $\bar\rho$.
Looking again at your question, the ...

answered Jun 26 '15 at 9:27

David Loeffler

28.5k33 gold badges6464 silver badges148148 bronze badges

15

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 to be `no'. Let's consider Goldbach's conjecture that every large integer $n$ is the sum of two primes. It is not hard to see from pigeonholing that the typical $...

nt.number-theory analytic-number-theory prime-numbers additive-combinatorics computational-number-theory

15

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). Note also that if $\zeta \not\equiv 1\pmod p$ satisfies $\zeta^3 \equiv 1\pmod p$ then $\zeta^2 + \zeta + 1 \equiv 0 \pmod p$, so
$$(x - \zeta y)(x - \zeta^2 y) =...

14

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)}{(x_1-x_2)(1-x_3)}$$ does the trick. (This is the same argument as in this answer.)
Note that these $w$ usually won't be algebraic integers, and they cannot be ...

14

[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 miss" that I know of is $13^5 + 16^5 = 17^5 + 12$.

13

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" (Mathematics of Computation, v. 56 (1991), 329-347). Another algorithm appears in the paper by B. Allombert, "Explicit computation of isomorphisms between finite ...

computational-complexity computability-theory finite-fields computer-algebra computational-number-theory

13

In Sage you can do something like:
x=polygen(QQbar)
f=x^5 - x +1
roots = f.roots(QQbar)
a1 = roots[1][0]
a2 = roots[-1][0]
(a1 - a2).minpoly()
x^20 - 10*x^16 - 95*x^12 + 625*x^10 - 40*x^8 + 3750*x^6 + 400*x^4 + 5000*x^2 + 2869

answered Sep 3 '17 at 18:59

Moritz Firsching

8,96022 gold badges4949 silver badges7474 bronze badges

13

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 < N$. Such a champion value $N$ for the divisor function was termed by Ramanujan as a highly composite number, and he determined the prime factorization of ...

13

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 which starts at a value $x_0$ and, for constants $c_1,c_2$ moves at step $k$ with probability $\frac{c_1}{\log^2 k}$ and, if so, increases or decreases by $\...

12

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. In particular, Theorem 2.1 gives a combinatorial interpretation of the coefficients of the polynomial $(1-x)^{2k+1}\sum_j e_k(j)x^j$, but I am unaware of a ...

answered Sep 4 '17 at 17:43

Richard Stanley

40.1k1010 gold badges138138 silver badges228228 bronze badges

12

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 >0$ that there is a $K=K_\epsilon>0$ so that
$$
a^x \le K\prod_{p\mid ab(a^x-b^y)} p^{1+\epsilon}
\le K(ab(a^x-b^y))^{1+\epsilon}.
$$
Replacing $K$ with a ...

answered Oct 20 '17 at 13:22

Joe Silverman

39.1k22 gold badges113113 silver badges202202 bronze badges

12

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 large number field. This is the step where GRH is used: it allows you to assume that the class group is generated by the set of prime ideals up to a relatively ...

ag.algebraic-geometry nt.number-theory elliptic-curves computational-number-theory riemann-hypothesis

10

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 explicit $q$-expansion formulae (involving sums of divisors, etc). The pairwise products of these series span the space of forms of weight 2. So if $F$ is the ...

answered Oct 25 '15 at 14:35

David Loeffler

28.5k33 gold badges6464 silver badges148148 bronze badges

10

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 Funktionenkörper, Abh. Math. Sem. Univ. Hamburg 14 (1941), 197-272.

10

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

answered Sep 4 '17 at 14:24

Fedor Petrov

78.6k77 gold badges180180 silver badges328328 bronze badges

10

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 rational $u$ in terms of natural numbers $\frac{pq+r}{p}$. Then $\lfloor u \rfloor = q$. The recurrence relation is now
$$
u_{n+1} = q_n (\frac{pq_n+r_n}{p} − ...

nt.number-theory ds.dynamical-systems sequences-and-series computational-number-theory discrete-dynamical-systems

10

As discussed in the comments, I don't see how to extract the desired matrix from the original question (about spanning the vector space). However, the matrix being nonzero IS equivalent to the following:
The polynomials $\sum_{i = 0}^{p-2} (i+1)^{-1} t^{i+n}$ for $0\leq n\leq p-2$, along with the polynomial $t^{p-1}$, span the vector space $\mathbb{F}_p[t]/(...

nt.number-theory prime-numbers matrix-theory computational-number-theory modular-representation-theory

9

The expression converges to $0$, even when $\phi(n)$ is replaced by the larger $n$. The contribution from $n\le\sqrt N/d$ can be given by ignoring the logarithm in the denominator:
\begin{align*}
\frac1{N^2} \sum_{d=1}^N \log d \sum_{n=1}^{\sqrt N/d} \frac{\phi(n)}{\log dn} &\le \frac1{N^2} \sum_{d=1}^N \log d \sum_{n=1}^{\sqrt N/d} n \\\
&\lesssim \...

nt.number-theory analytic-number-theory asymptotics additive-combinatorics computational-number-theory

9

Using resultants can greatly help. For example, knowing that $\sqrt[5]{2}$ is a zero of $P(x)=x^5-2$ and $1-\exp\frac{2\pi i}{5}$ is a zero of $Q(x)=(x-1)^5+1$, we conclude $\sqrt[5]{2}\cdot (1-\exp\frac{2\pi i}{5})$ is a zero of $\mathrm{Res}_y(P(y),y^5Q(\frac{x}{y}))$. In PARI/GP:
? polresultant(y^5-2,y^5*((x/y-1)^5+1),y)
%1 = x^25 + 2500*x^15 + 50000*x^5
...

9

A standard way to measure the size (= complexity) of vectors with coordinates in $\overline{\mathbb Q}$ is through the theory of Weil height functions. You can find the definition and properties of the Weil height
$$ H : \mathbb P^n(\overline{\mathbb Q}) \longrightarrow [1,\infty) $$
in many places, such as [1] and [2]. Since you are asking about vectors, ...

answered Jan 3 '18 at 18:03

Joe Silverman

39.1k22 gold badges113113 silver badges202202 bronze badges

9

You can check the current status (updated hourly). Currently among the different stats are:
All exponents below 46 251 389 have been tested and verified.
All exponents below 82 038 613 have been tested at least once.

answered Jan 16 '18 at 17:44

Aaron Meyerowitz

28.1k11 gold badge3939 silver badges9595 bronze badges

9

given your interest: the list of all $A x^2 + B y^2 + C z^2$ with ordered positive coefficients, such that the represented numbers can be described by congruences
Ummm. Allowing mixed terms, all 913 (probably) regular positive forms

nt.number-theory co.combinatorics additive-combinatorics computational-number-theory sums-of-squares

9

Seems that here is a proof that the graph is connected
Let $C$ be a component.
$C$ contains an even number, as an odd number $2k+1$ is adjacent to $2k(k+1)$.
$C$ contains a number divisible by $6$: if $2k\in C$ with $3\nmid k$, then $k^2-1\in C$ as well.
If $3k\in C$ and $p$ is a prime, then $3kp\in C$. Induction on $p$. The base cases $p=2,3$ follow ...

8

I recently implemented an algorithm to determine these number fields by computing
the $j$-polynomial: Let $\varphi: X_0(N) \to E$ be a fixed modular parametrization
and $P \in E(\mathbb{Q})$. By j-polynomial I mean the polynomial $F_P(x) = \prod_{z : \varphi(z) = P}(x - j(z))$. There's a Laurent
series $x(q)$ with integer coefficients, which is the modular ...

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

#### Related Tags

computational-number-theory × 320nt.number-theory × 233

prime-numbers × 48

algorithms × 44

computational-complexity × 40

analytic-number-theory × 38

algebraic-number-theory × 33

reference-request × 21

co.combinatorics × 19

diophantine-equations × 17

polynomials × 15

modular-forms × 14

elliptic-curves × 13

computer-algebra × 13

ag.algebraic-geometry × 12

factorization × 11

ac.commutative-algebra × 8

linear-algebra × 7

arithmetic-geometry × 7

additive-combinatorics × 7

gr.group-theory × 6

ds.dynamical-systems × 6

na.numerical-analysis × 6

computability-theory × 6

computer-science × 6