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).
258
questions
1
vote
0
answers
56
views
Effective Erdős–Kac theorem
I have some number $N$ and some integer $k>0$. I want to know what fraction of numbers up to $N$ have more than $k$ prime factors. (In my application, with repetition, but the $\omega$ version is ...
4
votes
0
answers
66
views
Adjoining new factors for primes in UFDs
It is well-known that if we pass from a UFD to a new ring where we have factored one of the primes, it does not need to stay a UFD. The classic example is passing from $\mathbb{Z}$ to $\mathbb{Z}[\...
3
votes
1
answer
347
views
The smallest solution to $2^{2k}-1=\text{powerful}$
Integer is powerful if all the exponents in its factorization are at least $2$.
Every powerful integer can be written in the form $a^2 b^3$.
For odd $k$, define $F(k)=2^{2k}-1=(2^k-1)(2^k+1)$.
This ...
1
vote
0
answers
62
views
Primality testing by reversible computation using the prime number theorem
Suppose we want to build a primality testing algorithm for the numbers limited to the set $A =\{1, ..., 2^n\}$ and $n$ is reasonably large. The prime-number theorem tells us that there are ...
10
votes
1
answer
306
views
Fixpoints of $m\longmapsto \mathrm{rad}(\phi(m^2))$ under iteration
Given a strictly positive integer $m$ let $\alpha(m)=\mathrm{rad}(m\phi(m))$
be the radical (product of all distinct prime divisors) of the product of $m$ and of Euler's totient function $\phi(m)=m\...
2
votes
2
answers
319
views
Uniqueness of sum of squares representation
Given a polynomial $f(x) \in \mathbb{R}[x] = \mathbb{R}[x_{1},\dots,x_{n}]$. We say $f(x)$ is sum of squares(SOS) if there are polynomials, $p_{1},\dots,p_{k}$ such that $f = p_{1}^{2} + \dots+p_{k}^{...
0
votes
1
answer
148
views
Coefficients of 0,1-polynomials factorization
Let $n\in\mathbb{N}$ and $P_{n}$ is $0,1$-polynomial whose coefficients are binary digits of $n$.
Let $Q_{1}(x) \cdot Q_{2}(x) \cdots Q_{m}(x)$ - polynomial factorization (over integers) of $P_{n}$.
...
0
votes
0
answers
62
views
Reference Request: Factorization method for polynomials whose maximum absolute value of coefficient is 1
So, today I came up with a method for factoring polynomials whose coefficients are either $-1$ or $1.$
Let me explain with examples.
Example No. 1. Factorize $P(x)=x^8+x^7+1$
Solution. It is known ...
0
votes
1
answer
197
views
Simple question about 0,1-polynomials
Being interested in these polynomials, would like to clarify one small observation.
Let $n\in\mathbb{N}$ and $P_{n}$ is $0,1$-polynomial whose coefficients are binary digits of $n$.
Let $n$ has prime ...
3
votes
1
answer
75
views
Evaluating the generalized continued fraction obtained from the factorization of a bivariate polynomial equation
Happy New Year, MO community!
We need someone expert in Generalized Continued Fractions (GCFs), with a deep knowledge of the GCFs’ convergence properties, to solve the following problem.
PROBLEM
...
0
votes
0
answers
71
views
On the multiplicative group of quotients of polynomial rings
Related to this.
The $p+1$ factorization algorithm works over $\mathbb{Z}/n\mathbb{Z}[x]/f(x)$
and hopes $p+1$ to be smooth.
We are trying to generalize this to multivariate case
and also try to find ...
4
votes
0
answers
135
views
Has anyone studied factoring as a CO-product?
In factorization, like integer factorization, you start with an integer and end up with a kind-of list of pairs of other elements, namely the factors.
I want to explore the "Co-ness" of this....
3
votes
3
answers
367
views
Closed formula for number of ones in a proper factor tree
Edit [2023 Dec 7]: One of my specific wonders, along with that of students, is around when a recursive formula might have – or be expected to have – an explicit or closed formula. What is the ...
0
votes
0
answers
20
views
Low-rank factorization of a Finite Element matrix
I have a matrix $M\in \mathbb R^{n\times n}$, stemming from a Finite Element discretization of an advection function.
I want to find a factorization $ M= S E T $ with $S, T\in \mathbb R^{n\times s}$ ...
2
votes
1
answer
266
views
Is there a combinatorial interpretation for the change of basis matrix in the Frobenius normal form representation?
Let $G$ be a graph on $n$ vertices. Let $A$ be the adjacency matrix of $G$ (i.e., rows and columns of $A$ are indexed by vertices of $G$, and the $(v,w)$ entry of $A$ is $1$ if $(v,w)$ is an edge in $...
2
votes
1
answer
141
views
How to do LU factorization efficiently based on the factorized result added with a low-rank matrix?
Suppose a square $n\times n$, dense matrix $A^{\text{old}}$ has been factorized into $L^{\text{old}}$ and $U^{\text{old}}$ components by performing a LU decomposition $A^{\text{old}} = L^{\text{old}}U^...
0
votes
2
answers
297
views
A doubt regarding the extended form of the Weierstrass factorization theorem
I want to represent $\sin(x)-\dfrac{1}{\sqrt{2}}$ as a product of it's zeroes
According to the Weierstrass factorization theorem, the sine function can be represented as a product of its factors:
$$\...
4
votes
1
answer
196
views
Representation of a number as a product of $\sqrt{n^2 + 1} + n$
Question. Do there exist two multisets $A, B$ consisting of positive integer numbers such that $|A|$ and $|B|$ have different parity and
$$
\prod_{n\in A}(n + \sqrt{n^2 + 1}) = \prod_{m\in B}(m + \...
2
votes
1
answer
319
views
Modular square roots problem which is $NP$ hard
It is well known extracting modular square roots modulo a composite number factors the modulus.
On other hand given $u,v>0$ and an integer $n$, deciding if there is a factor of $n$ in $[u,v]$ is $...
0
votes
0
answers
26
views
How to compute a smooth number over a factor base in General Number Field Sieve (GNFS) factoring algorithm?
Following this on page 12, I understand the first steps of the general number field sieve (GNFS) algorithm for factoring as follows:
Step 1:
Let
$$N = 77$$
and choose
$$m = 4$$
Then
$$N=77 = 1(4^3) + ...
2
votes
0
answers
186
views
Factorization of the polynomial $x^k + x^{k-1} + x^{k-2} + \cdots + x + 1$ in $\mathbb{F}_2[x]$ [closed]
Is anything known about the factorization of the polynomial $x^k + x^{k-1} + x^{k-2} + \cdots + x + 1$ in $\mathbb{F}_2[x]$?
When can it be factored, what are the irreducible factors, what are the ...
1
vote
0
answers
71
views
Factorising a multivariate polynomial, in terms of products of linear polynomials, using blowups
I am considering multivariate polynomials of the form
$$f(x,y)=x^a\,y^b\,p(x,y)^c$$
(and similarly for higher dimensions). I am trying to transform these polynomials into the generic form
$$\widetilde{...
1
vote
0
answers
33
views
Number of right divisors of a central skew polynomial
Let $\mathbb{F}$ be a finite field of $p$ elements, $\sigma \in \operatorname{Aut}(F)$ of order $m$, $\mathbb{F}^\sigma$ be the fixed field of $\sigma$, and $\mathbb{F}[x,\sigma]$ be a skew polynomial ...
5
votes
0
answers
160
views
Reducibility of $f(x)^{2^n}+1$ and $f(x)^{2^n}+g(x)^{2^n}$
Related to generalized Fermat numbers.
Let $f(x),g(x)$ be coprime polynomials with integer coefficients.
Assume that if $f(x)$ or $g(x)$ are of the form $h(x)^k$ then $k$ is power
of two.
Q1 Is it ...
2
votes
0
answers
59
views
Factor group of all the sequences by the subgroup of bounded sequences
Consider the group G of the sequences of real numbers (the group operation is addition). It contains a subgroup H of bounded sequences.
Is there any nice description of the factor group G/H ?
It is ...
6
votes
0
answers
166
views
$p^2+a^2$ can be a squarefree number with all prime divisors less than $p$?
Let $p$ be a prime $\ge 31$.
Is there an integer $a < p$ such that $p^2 + a^2$ is a squarefree and all of its prime divisors are less than $p$?
For example, for $p=31$, $31^2+5^2 = 986 = 2 \times ...
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 ...
4
votes
0
answers
61
views
weak factorization systems (co)generated by an arbitrary class of morphisms
Under what assumptions can one prove existence of weak factorization systems (co)generated by a class of morphisms ?
Are there counterexamples ? I am interested both in assumptions on the class of ...
4
votes
3
answers
387
views
Can nonnegative functions $f(x,y,z)$ be written as a product of pairwise functions $u(x,y) v(y,z) w(x, z)$?
In my course on probabilistic graphical models, my professor made a claim which I find a little sus. In discussing the equivalence between Markov Random Fields and Factor Graphs, the following example ...
1
vote
0
answers
18
views
Optimal Truncation of LDL-factorization to improve conditioning
Suppose I factored real symmetric quasi-definite $ A_0= L_0 \cdot D_0 \cdot L_0^T$ and the factorization exists, with $D$ diagonal and $L$ unit lower-triangular; and suppose $L$ and $D$ are badly ...
1
vote
0
answers
33
views
Slope assertion in Cholesky on digital computers
For a real symmetric positive definite linear system
$$ A \cdot x = b, $$
solved using Choelsky with forward- and backward-substitution, we know it for the numerical approximation $\tilde{x}$ to $x$ ...
3
votes
2
answers
198
views
Practical symmetric equivalent to QR factorization updates
As we know, the QR-factorization $Q\cdot R=A$ of any real symmetric $n \times n$ matrix $A$ with full rank is unconditionally numerically stable. Further, when A is rank-1-updated, the factorization ...
2
votes
0
answers
67
views
Twin prime distribution centering twice a semiprime
What is the conjectured distributional behavior of semiprimes $pq$ ($p$ and $q$ are primes) having the property $2pq+1$ and $2pq-1$ are primes?
1
vote
0
answers
62
views
Distribution of number of prime factors of $p^k\pm1$
What is the behavior of number of prime factors of integers of form $p^k\pm1$ where $p$ is a fixed odd prime or $2$ and $k$ varies over positive integers?
1
vote
0
answers
68
views
Is this factorization problem in EXP?
Factorization is not known to have a polynomial time algorithm. Traditionally the input length is number of bits in representation of the integer to be factored.
However now consider integers of form $...
2
votes
0
answers
85
views
How to decompose a matrix over a ring $F[X_1,\ldots,X_k]$ as a product of two matrices
Let $F$ be a field. Assume any reasonable conditions if needed, such as $F=\mathbb R$, $F=\mathbb C$, $F$ is a finite field, or $F$ has a specific characteristic, etc. Let $C$ be an $n\times1$ matrix ...
4
votes
2
answers
183
views
Counting integers with k large prime divisors
If $x \ge y \ge 1$ are real numbers and if $k$ is a positive integer, take $\Phi_k(x, y)$ to be the number of integers $\le x$ with exactly $k$ prime factors and no prime factor $\le y$. If $y$ is ...
3
votes
0
answers
107
views
Could a quantum computer factor $N=p\times q$ using Hadamard transforms on $x^2\bmod N$ (instead of Fourier transforms on $a^x\bmod N$)?
In Classically verifiable quantum advantage from a computational Bell test, Kahanamoku-Meyer, Choi, Vazirani, and Yao propose using $x^2 \bmod N$ in an interactive proof-of-quantumness. This is a two-...
0
votes
0
answers
167
views
How many elements have a "small" order in a finite field?
I'm hoping that this is an easy question for someone.
How many elements can we expect to have multiplicative order at most $n^{1/c}$ in one of the finite fields $\mathbb{F}_p$ with $p$ prime with $n \...
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 ...
1
vote
0
answers
121
views
Removing intermediate terms from a $10^{\text{th}}$-degree polynomial
When given a tenth degree polynomial
$$f(x)=\sum_{n=0}^{10} a_n x^n$$
I wish to compute an inverse via the Lagrange inversion theorem to produce a generalized hypergeometric sum similar to a Bring ...
4
votes
0
answers
215
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 ...
1
vote
0
answers
124
views
What are the limitations for calculating the inverse of a polynomial with the Lagrange inversion theorem?
I have been attempting to produce a series expression for the roots of high degree polynomial using the Lagrange Inversion theorem. I am curious about the statement from the Wikipedia page on Bring ...
1
vote
0
answers
107
views
Polynomial divisible by unbounded primes with exponent one
Let $f(x)$ be squarefree polynomial with integer coefficients and
degree at least $3$.
Is it true that for all sufficiently large $n$, $f(n)$ is divisible
by prime $p$ with exponent one and $p$ is ...
1
vote
1
answer
170
views
On the sequence $a(n)=\gcd(2^n-1,\phi(2^n-1))$
For natural $n$, define the sequence
$$
a(n)=\gcd(2^n-1,\phi(2^n-1))
$$
It doesn't appear to be in OEIS and starts
$1,1,1,1,9,1,1,1,3,1,9,1,3,1,1,1,27,1,75,49$
Q1 Can we unconditionally prove $a(n)=1$...
0
votes
1
answer
180
views
Factor $\sum_{n=1}^{N} x^n$ [closed]
I am attempting to factor an $N^{\text{th}}$ degree polynomial with coefficients strictly equal to $1$ given by the equation
$$\sum_{n=1}^{N} x^n$$
Although the Galois group for anything beyond a ...
7
votes
1
answer
424
views
Do polynomial values rarely have large multiple prime factors?
I am interested in the following set-up:
Let $F \in \mathbb{Z}[x_1,\dots,x_n]$ be a fixed irreducible homogeneous polynomial of degree $d$ and consider the quantity
$$N_{\delta}(B)=\#\{(x_1,\dots,x_n) ...
2
votes
0
answers
87
views
A gsvd variation: Two SVDs with common matrix
The generalized singular value decomposition (gsvd) is described on wikipedia here. Since there are several conventions, I'll just briefly present one.
The "MATLAB" convention decomposes two ...
1
vote
0
answers
225
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\...
3
votes
0
answers
124
views
Order of elements $\gamma$ and $1-\gamma$ in $\mathbb{F}_q$
I'd like to find if possible the orders possible for $1-\gamma$ given a $\gamma\in\mathbb{F}_q$ of given order $\mathcal{o}$ (where $q=p^f$).
Which is clear is that these order have the same degree (...