Questions tagged [factorization]
For questions about factorization, the decomposition of mathematical objects (e.g. natural numbers, polynomials) into products of smaller objects (e.g. primes, lower degree polynomials).
35
questions
116
votes
5
answers
32k
views
How did Cole factor $2^{67}-1$ in 1903?
I just heard a This American Life episode which recounted the famous anecdote about Frank Nelson Cole factoring $N:=2^{67}-1$ as $193{,}707{,}721\times 761{,}838{,}257{,}287$. There doesn't seem to be ...
44
votes
1
answer
17k
views
Conjecturally unsafe RSA primes $p=27a^2+27a+7$
We got strong numerical evidence that primes of the form $p=27a^2+27a+7$
are unsafe for cryptographic purposes since they can be found in the factorization.
Consider the following generic factoring ...
9
votes
2
answers
533
views
Cubic graphs whose 2-factors all have the same cycle type
Let $G$ be a bridgeless cubic graph. I am interested in such graphs where all 2-factors are isomorphic (as graphs), i.e. have the same partition as cycle type. We'll say that this partition is ...
4
votes
1
answer
312
views
Generalizing Kasteleyn's formula even more?
Inspired and intrigued by this question, I decided just for fun to throw in another integer into the factors and look what happens. So for $k\in\mathbb Z$, let us define $$K_r(n,k):=\prod_{\ell_1=1}^...
4
votes
3
answers
2k
views
$2^n$-1 consisting only of small factors
I've checked the factorization of $2^N - 1$ up through N = 120 for the largest prime factor, and it looks like the largest value of N where $2^N-1$ has a largest prime factor under 2500 is N = 60 (...
33
votes
7
answers
3k
views
On the polynomial $\sum_{k=0}^n\binom{n}{k}(-1)^kX^{k(n-k)}$
Let $n = 2m$ be an even integer and let $F_n(X)$ be the polynomial $$F_n(X):=\sum_{k=0}^n\binom{n}{k}(-1)^kX^{k(n-k)}.$$ I observed (but cannot prove) that the polynomial $F_n$ is always divisible by $...
25
votes
1
answer
6k
views
Evidence for integer factorization is in $P$
Peter Sarnak believes that integer factorization is in $P$. It is a well-known open problem in TCS to identify the real complexity class of integer factorization. Take a look at this link for Peter ...
15
votes
6
answers
2k
views
Seeking Noetherian normal domain with vanishing Picard group but not a UFD
Once again, the question says it all.
My motivation is the article on factorization I am writing. I want to explain (as well as to understand!) why for normal Noetherian domains of dimension greater ...
15
votes
2
answers
938
views
Factorization when a factor is partially known
Let's say that I have a very large number of the order ($10^{250+}$) which is composite. I have been given one of its factor partially to a significant amount of digits (say 75+). Then, how can I ...
13
votes
2
answers
5k
views
Parametrization of positive semidefinite matrices
We know that a real, symmetric, positive definite matrix $A$ of size $n\times n$ can be parametrized by a vector $\theta$ of $\frac{n(n+1)}{2}$ parameters thanks to the Cholesky decomposition:
$$
A = ...
13
votes
3
answers
3k
views
Density of Irreducible Polynomials in $\mathbb{Z}[x]$
Recently I was thinking about some questions concerning $\mathbb{Z}[x]$ and realized that they might be a bit easier if I knew the relative densities of reducible polynomials.
Let $P_d$ denote the ...
12
votes
3
answers
3k
views
What is known about the polynomial factorization of power series?
Some power series factorize; $1+\sum_{n=1}^\infty x^n=\prod_{n=1}^\infty (1+x^{2^n})$ and $1+\sum_{n=1}^\infty x^{2n}/(2n+1)!=\prod_{x=1}^\infty (1+x^2/n^2\pi^2)$ for example; while others do not----...
12
votes
5
answers
2k
views
Polynomials all of whose roots are rational
I have two questions about the class of integer-coefficient polynomials all of whose roots are rational.
I asked this at MSE, but it attracted little interest (perhaps because it is not interesting!)
...
11
votes
2
answers
4k
views
How can one construct a sparse null space basis using recursive LU decomposition?
Given an $m$ by $n$ matrix $A$ I'm familiar with the standard method to compute a basis for the null space of $A$ by computing a QR factorization of $A^T$. If $A$ is large and sparse, we can use ...
10
votes
3
answers
3k
views
Reduction from factoring to solving Pell equation
The paper Polynomial-Time Quantum Algorithms for Pell's Equation and the Principal Ideal Problem claims
There are reductions from factoring to solving Pell’s equation, and from solving Pell’s
...
10
votes
1
answer
294
views
$2$-adic valuation of Schur $P$-functions in the power-sum basis
For a partition $\lambda$, let $P_\lambda$ be the Schur $P$-functions (case $t=-1$ of Hall-Littlewood symmetric functions) and let $p_\lambda=p_{\lambda_1}p_{\lambda_1}\cdots p_{\lambda_k}$ be the ...
10
votes
2
answers
17k
views
Fast trace of inverse of a square matrix
Which would be the most efficient way (in computational time) to compute tr(inv(H)), where H is a (dense) square matrix?
In my particular problem I also have a LU decomposition of H already available,...
10
votes
3
answers
2k
views
Irreducible/prime/indivisible elements
in what follows all the rings are commutative, nontrivial, with unit.
Recall the following definitions:
1) $\pi\in A$ is prime if $(\pi)$ is a nonzero prime ideal
2) $\pi\in A$ is irreducible if $\...
9
votes
1
answer
676
views
Hensel's lemma, Bezout's identity, and the integers
Factorization in the ring $\mathbb{Z}[x]/(x^2+1)\mathbb{Z}[x]\cong \mathbb{Z}[i]$ is well known. For instance, $5$ and $13$ (and any prime $\equiv 1\pmod{4}$) are no longer prime.
The factorization ...
9
votes
1
answer
567
views
Intuition for density comonad in relation to lifting problems
In Emily Riehl's Categorical Homotopy Theory, there is a section on Garner's Small Object Argument which I'm trying and failing to understand. Originally I followed most of Garner's paper, using the ...
9
votes
3
answers
972
views
$\omega(p^n - 1)$ as $n \rightarrow \infty$
Although I am also interested in the number of distinct prime factors (not counting
multiplicity), today I use $\omega(m)$ to denote the number of (positive) prime
factors (with multiplicity) of the ...
8
votes
1
answer
233
views
Functions over monoids which factor in two different ways
This is a follow-up question to this MO question, which was asked by Richard Stanley in a comment to my answer there.
Let $S$ be a commutative monoid and $f(x_1, \dots, x_n)$ be a function from $S^n$ ...
7
votes
1
answer
299
views
Large gaps between consecutive irreducible polynomials with small heights
For a prime gap of length at least $n$, a trivial upper bound for its first occurrence is $N=n!$ or $N=lcm(2,\dots,n)$. A bit better is $N=p_1\cdots p_n$ where $p_k$ is the $k$th prime, as then $N+2,\...
7
votes
0
answers
850
views
Optimal Gear Trains
Suppose you need to slow down a turning motor so that a gear turns at
an angular velocity $\frac{a}{b}$ of that of the motor shaft, where $a$ and
$b$ are natural numbers. For example, this set of ...
4
votes
0
answers
206
views
More 3-connected cubic graphs with all 2-factors of same cycle type?
The setup is as in this question: Let $G$ be a 3-connected cubic graph. If all 2-factors of $G$ are isomorphic (as graphs), i.e. all have the same partition $\pi$ as cycle type, we'll say that $G$ is ...
4
votes
0
answers
214
views
Characterizing atomicity in a commutative domain
In Proposition 1.1 of [Math. Proc. Cambridge Phil. Soc. 64 (1968), No. 2, 251-264], P.M. Cohn famously claimed (without proof) that a commutative domain is atomic if and only if it satisfies the ...
3
votes
1
answer
131
views
Factoring $x^p H(x) + x^q B(x) + T(x)$ over a finite field
$\newcommand\S{\mathcal S}$
Let $p$ be a prime, and suppose that $0.9(p-1)<q<p-1$. Suppose, furthermore, that $H,B,T\in\mathbb F_p[x]$ satisfy $\max\{\deg H,\deg T\}\le q-1$ and $\deg B\le p-1-q$...
3
votes
1
answer
488
views
How much space between these smooth numbers?
In looking at OEIS sequence A063539, $1,8,12,16,18,24,27,30,32,36,40,45,...$ I noticed that the first 1000 members were less than 4000, and thought there were no large gaps between them. What (if ...
3
votes
1
answer
3k
views
Uniqueness of the reduced rank QR decomposition
Let $A$ be a $n\times n$ matrix that is a real, symmetric, positive semidefinite and has rank $r$.
I read about the rank reduced $QR$ decomposition (here for example) as the QR variant where $A=QR$ ...
3
votes
0
answers
67
views
Atomicity and BF-ness in monoids of integer points of a polyhedral cone of $\mathbb R^n$
Fix an integer $n \ge 2$ and let $H$ be the (additive) monoid of integer points of a polyhedral cone of the Euclidean space $\mathbb R^n$ with the additional property that $H \setminus \{0_n\}$ is ...
2
votes
1
answer
354
views
Positive divisors of $P(x,n)=1+x+x^2+ \cdots + x^n$ that are congruent to $1$ modulo $x$
This is a follow-up question to Positive integer solutions to the diophantine equation $(xz+1)(yz+1)=z^4+z^3 +z^2 +z+1$
Let \begin{equation}
P(x,n)= 1+x+x^2+ \cdots + x^n, \end{equation}
\begin{...
2
votes
1
answer
376
views
Irreducibility of Faulhaber-like Polynomials over $\mathbb Q[x]$
Motivation: Inspired by the famous Faulhaber polynomials $F_k(N)=\displaystyle\sum_{n=0}^Nn^k,$ I decided to study their alternating versions, $\Phi_k(M)=\displaystyle\sum_{n=0}^M(-1)^nn^k$.
For $k\...
1
vote
0
answers
223
views
Construct special "joint SVD" from separate SVDs
Given two matrices, $A,B\in\mathbb{C}^{n\times n}$ which can be written as
$$ A = XD_AY^T \\
B = XD_BY^T $$
where $X$ and $Y\in\mathbb{C}^{n\times n}$ are unitary and with diagonal $D_A$ and $D_B\in\...
1
vote
2
answers
367
views
When is a prime factor of Mersenne number Wieferich prime?
Wieferich prime is a prime number $p$ such that $p^2$ divides $2^{p - 1} - 1$.
There are only two Wieferich primes known and it is an open problem if
there are infinitely many non-Wieferich primes.
...
0
votes
1
answer
255
views
Infinite products for linear combinations of sines or cosines
There is a well known infinite product both for $\phi(x)=\sin x$ and $\phi(x)=\cos x$. These are particular cases of the Weierstrass factorization theorem. What about
$\phi(x)=a_1\cos b_1 x + a_2\cos ...