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).
240
questions
1
vote
0
answers
21
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 ...
- 323
2
votes
0
answers
55
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 ...
- 4,661
6
votes
0
answers
155
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 ...
- 435
4
votes
0
answers
54
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 ...
- 503
1
vote
0
answers
12
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 ...
- 51
1
vote
0
answers
30
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$ ...
- 51
4
votes
3
answers
351
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 ...
- 85
3
votes
2
answers
106
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 ...
- 51
1
vote
0
answers
83
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 $...
- 13.2k
2
votes
0
answers
58
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?
- 13.2k
1
vote
0
answers
57
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?
- 13.2k
1
vote
0
answers
57
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 $...
- 13.2k
2
votes
0
answers
75
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 ...
- 121
3
votes
0
answers
90
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-...
- 2,113
0
votes
0
answers
156
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 \...
- 221
0
votes
0
answers
17
views
Identifying redundant vectors In non-negative matrix bases
I have a target non-negative matrix $X$ that I would like to factor.
I have two non-negative matrices $W$ and $H$ such that $WH = X$. In this formulation, the rows of $H$ are $L^2$ normalized and ...
- 13
3
votes
0
answers
64
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 ...
- 9,020
1
vote
0
answers
104
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 ...
- 577
4
votes
0
answers
206
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 ...
- 9,020
1
vote
0
answers
116
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 ...
- 577
1
vote
0
answers
105
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 ...
- 23.8k
1
vote
1
answer
146
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$...
- 23.8k
0
votes
1
answer
170
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 ...
- 577
7
votes
1
answer
398
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
47
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 ...
- 61
1
vote
0
answers
151
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\...
- 61
3
votes
0
answers
123
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 (...
- 265
1
vote
1
answer
120
views
Order of roots for a polynomial $P\in\mathbb{F}_p[T]$
Let $P\in\mathbb{F}_p[T]$ (not supposed irreducible). All roots $\xi$ of $P$ have a certain order $k$ such that $\xi^k=1$.
Question: is it possible to know the order of the roots of the given ...
- 265
0
votes
0
answers
161
views
From direct sum of quotient group of a group to direct sum of the group
We know that for a cyclic group $G$, if $G=A\oplus B$, then for some subgroups $H$ of $G$, We have $G/H=(A+H)/H\oplus (B+H)/H.$ But, if we know that for a subgroup $H$ of $G$, $G/H=(A+H)/H\oplus (B+H)...
- 21
1
vote
0
answers
88
views
What is the factorization algebra/space of an affine W algebra?
The affine vertex algebra $V_k(\mathfrak{g})$ factorizes, i.e. comes from a factorisation space, the Beilinson Drinfeld Grassmannian. Similarly, lattice vertex algebras have a factorization analogue.
...
- 5,112
2
votes
1
answer
298
views
Eisenstein polynomial of totally ramified extension over $p$-adic field
Let $p\geq 3$ be a prime number, $K$ be a finite extension of $\mathbb{Q}_p$ with no non-trivial unramified subextension, $f(x)$ be an irreducible monic polynomial in $\mathcal{O}_K[x]$, making $L=K[x]...
- 507
12
votes
1
answer
555
views
Would efficient factoring have any *other* useful applications?
This question is certainly somewhat opinion-based, but hopefully not hopelessly so.
The granddaddy of all applications for an efficient period finding or factoring capability (e.g. Shor's algorithm) ...
- 1,213
10
votes
1
answer
296
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\...
- 15.9k
0
votes
0
answers
34
views
Number of different factorizations
I define $\nu(n)$ the number of different factorizations for an integer $n$. I know there are papers about $\delta(n)$ the number of dividers for an integer $n$ (Landau, Euler, Dirichlet) but I still ...
3
votes
1
answer
139
views
Factoring higher-order differential operators
I have been researching various methods for solving differential equations. In particular, I want to better understand the factoring approach. For example, if we want to solve a general second order ...
- 51
1
vote
2
answers
324
views
Does having the discrete logarithm of prime factors of $n$ allow us to calculate any discrete log more efficiently?
Let $(p_1)^{k_1}(p_2)^{k_2}\dots$ be the prime factorization of $\varphi(n)$. Assuming that we have a value of order $(p_x)^{k_x}$ for all $x$, can we calculate the discrete log of any value in $\...
- 221
6
votes
1
answer
903
views
Solution to sixth order equation
I'm dealing with the expression $x = \frac{1}{3}y(y+1)(2y+1)^2(2y^2+2y+1)$. What is this approximately, if one is explicitly writing y in terms of x? There's no general formula for sixth powers ...
- 807
4
votes
1
answer
176
views
Groups suitable for algebraic group factorizations of integers
Quoting Wikipedia on Algebraic-group factorisation algorithm
Algebraic-group factorisation algorithms are algorithms for factoring an integer N by working in an algebraic group defined modulo N whose ...
- 23.8k
5
votes
0
answers
144
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 ...
- 23.8k
1
vote
0
answers
40
views
Systematic approach to Weierstrass factorization
If you want to calculate the Taylor expansion of a function, you only need to know the derivatives of the function at the point of expansion.
Is there a similar algorithmic approach that can be ...
- 323
3
votes
0
answers
128
views
Integers with exactly three factor pairs whose successors are relatively prime
I am interested in the following problem, and will appreciate pointers around how it can be solved – partially or fully – and/or indicators around whether it is even tractable:
Characterize $N \in \...
- 7,446
9
votes
1
answer
604
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 ...
- 17.3k
1
vote
0
answers
133
views
Factorization of argmax
We consider a function $f(s_{1:p}, a_{1:p})$, where $p>1$ is an integer, $s_{1:p}$ denotes $(s_1,\ldots,s_p)^\top \in R^p$, and $a_{1:p}$ denotes $(a_1,\ldots,a_p)^\top \in R^p$.
Question: What is ...
- 1,107
2
votes
1
answer
333
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{...
- 319
0
votes
0
answers
136
views
A diophantine equation involving partial sums of exponentials similar than the equation in Fermat's Last Theorem
I'm curious about the following diophantine equation from my invention: I don't know if this is in the literature, I wrote it using creativity in an attempt to write a variant of the equation in ...
10
votes
1
answer
245
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 ...
- 2,382
3
votes
0
answers
93
views
Next smooth number
I want to find the next $n \in \mathbb{N}$ such that
$$s < n = \prod_{p_i \in \mathbb{P}_B} {p_i}^{a_i}$$
Where $\mathbb{P}_B$ is the set of primes not greater than $B$
I know that we can generate ...
- 131
1
vote
0
answers
123
views
Need help interpreting this formula for the number of Goldbach partitions [closed]
1: Formula for the number of Goldbach partitions.
Let $g\left(n\right)$ denote the number of Goldbach partitions of even integer $2n$:
$$g_{\left(n\right)}=\sum_{3\leq p\leq2n-3}\left[\pi\left(2n-p\...
- 197
8
votes
1
answer
228
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$ ...
- 29.8k
4
votes
1
answer
294
views
Numbers with large prime exponents and the ABC conjecture
By Fermat's Last Theorem, there are no solutions to the Diophantine equation $a^n + b^n = c^n$ for $a,b,c > 0$ and $n>2$. Beal's conjecture allows the exponents to be different (but also $>...
- 43