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

Filter by
Sorted by
Tagged with
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 ...
user1747134's user avatar
0 votes
1 answer
147 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}$. ...
Denis Ivanov's user avatar
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 ...
Vanya Borisyuk's user avatar
0 votes
1 answer
196 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 ...
Denis Ivanov's user avatar
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 ...
joro's user avatar
  • 24.2k
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 ...
Monk's user avatar
  • 125
4 votes
0 answers
133 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....
Ben Sprott's user avatar
  • 1,319
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}^{...
wsz_fantasy's user avatar
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 ...
Benjamin Dickman's user avatar
0 votes
0 answers
19 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}$ ...
MisterWulf's user avatar
2 votes
1 answer
138 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^...
Alex Joe's user avatar
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: $$\...
LithiumPoisoning's user avatar
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 $...
Naysh's user avatar
  • 455
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 + \...
Pavel Gubkin's user avatar
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) + ...
James's user avatar
  • 109
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 ...
José's user avatar
  • 209
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{...
Giulio Crisanti's user avatar
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 ...
a196884's user avatar
  • 323
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 ...
Nikita Kalinin's user avatar
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 ...
P.-S. Park's user avatar
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 ...
user494312's user avatar
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 ...
kaisong's user avatar
  • 51
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$ ...
kaisong's user avatar
  • 51
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 ...
bucket's user avatar
  • 85
3 votes
2 answers
195 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 ...
kaisong's user avatar
  • 51
2 votes
1 answer
318 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 $...
Turbo's user avatar
  • 13.7k
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?
Turbo's user avatar
  • 13.7k
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?
Turbo's user avatar
  • 13.7k
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 $...
Turbo's user avatar
  • 13.7k
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 ...
zxcv's user avatar
  • 131
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-...
Mark S's user avatar
  • 2,143
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 \...
Matt Groff's user avatar
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 ...
Salvo Tringali's user avatar
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 ...
Talmsmen's user avatar
  • 547
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 ...
Salvo Tringali's user avatar
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 ...
Talmsmen's user avatar
  • 547
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 ...
joro's user avatar
  • 24.2k
1 vote
1 answer
166 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$...
joro's user avatar
  • 24.2k
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 ...
Talmsmen's user avatar
  • 547
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) ...
Christian Bernert's user avatar
2 votes
0 answers
83 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 ...
sqrt6's user avatar
  • 61
1 vote
0 answers
224 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\...
sqrt6's user avatar
  • 61
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 (...
Gabriel Soranzo's user avatar
1 vote
1 answer
181 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 ...
Gabriel Soranzo's user avatar
0 votes
0 answers
193 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)...
user110901's user avatar
2 votes
0 answers
109 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. ...
Pulcinella's user avatar
  • 5,506
2 votes
1 answer
427 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]...
Yijun Yuan's user avatar
13 votes
1 answer
643 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) ...
tparker's user avatar
  • 1,243
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\...
Roland Bacher's user avatar
0 votes
0 answers
37 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 ...
Aileann D. PRET's user avatar

1
2 3 4 5 6