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).
219
questions
3
votes
0
answers
78
views
Construct a special kind of SVD
Given two matrices, $A,B\in\mathbb{C}^{n\times n}$ which can be written as
$$ A = XD_AY^H \\
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\...
- 71
1
vote
0
answers
80
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\...
- 71
3
votes
0
answers
118
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
76
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
97
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
0
votes
0
answers
57
views
Sampling a distribution related to factoring
Consider these two problems.
Given two numbers $a$ and $N$, find the smallest $r$ such that $a^r= 1 \pmod N$.
Given three numbers $a$, $r$, and $N_{max}$, find $N\le N_{max}$ such that $a^r= 1 \pmod ...
- 333
1
vote
0
answers
51
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.
...
- 4,004
2
votes
1
answer
217
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]...
- 417
0
votes
0
answers
46
views
Partition of multisets of polynomials
Problem: Given a multiset $S$ of irreducible polynomials in $\mathbb{Z}[x]$, say YES if $S$ can be partitioned into two nonempty multisets $A$ and $B$ such that both the product of all the elements of ...
- 1
12
votes
1
answer
509
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) ...
- 765
10
votes
1
answer
273
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\...
- 13.6k
0
votes
0
answers
28
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
92
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
160
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
843
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 ...
- 461
4
votes
1
answer
167
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.3k
4
votes
0
answers
97
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.3k
1
vote
0
answers
36
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 ...
- 305
3
votes
0
answers
117
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,176
9
votes
1
answer
532
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 ...
- 14.8k
1
vote
0
answers
125
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,347
2
votes
1
answer
317
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{...
- 269
0
votes
0
answers
135
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 ...
- 37
10
votes
1
answer
186
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 ...
- 1,663
3
votes
0
answers
84
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
103
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\...
- 205
8
votes
1
answer
223
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$ ...
- 28.7k
4
votes
1
answer
271
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
5
votes
1
answer
364
views
When $p(x)^2 \mid f(g(x))$?
Let $f(x),g(x),p(x)$ be non-constant polynomials with rational coefficients.
Is it true that for all $f$ exist $g,p$ such that $p(x)^2 \mid f(g(x))$?
Partial results:
$f(g(x))$ is divisible by square ...
- 23.3k
3
votes
1
answer
181
views
Do there exist irreducible elements in this domain?
I asked this question on MSE. Here also I have the same motive in the question.
Let $D= \{\,a_1x^{r_1} + \cdots + a_n x^{r_n} \, \vert \, a_i \in \mathbb{C} \text{ for } i= 1,2,\dots,n \text{ and ...
- 145
3
votes
1
answer
207
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 ...
- 23.3k
3
votes
1
answer
438
views
Must Mersenne numbers be divisible by arbitrary large primes with exponent one?
Let $M_n$ denote the Mersenne numbers $M_n=2^n-1$.
As $n$ varies, must $M_n$ be divisible by arbitrary large prime $p$
with exponent one, i.e. $p \mid M_n, p^2 \nmid M_n$?
In other words, must the ...
- 23.3k
1
vote
2
answers
252
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.
...
- 23.3k
2
votes
0
answers
156
views
Factoring integers of the form $n=p q^2$ using elliptic curves
We got argument and strong experimental support
that integers of the form $n=p q^2$ can
be factored using elliptic curves easier than general integers
Q1 Is this known?
Added This is known since at ...
- 23.3k
0
votes
0
answers
170
views
Functor factorization theorem and the structure of a functor
Corollary 4.8 in Awodey's book states that every functor $\mathcal F$:$\mathcal C$$\rightarrow$$\mathcal D$ factors $\mathcal F$ = $\mathcal H$ ◦ $\mathcal G$ where
$\mathcal G$ : $\mathcal C$$\...
- 77
1
vote
0
answers
85
views
Smooth number pairs satisfying a congruence
Let $\mathcal P=\{p_1,\dots,p_{2t}\}$ be $2t$ primes between $2^\ell$ and $2^{\ell+1}$ and fix an exponent bound $a\in\mathbb Z_{\geq2}$.
Fix $N\in\mathbb N$ whose prime factors $p$ satisfy $p>2^{\...
- 12.8k
2
votes
1
answer
136
views
Are there any homomorphic analog error correction code?
Are there any analog error correction codes that are additively and multiplicatively homomorphic?
- 41
1
vote
0
answers
60
views
Factoring a complex function such that it is analytic in upper and lower plane
Consider this function $$\frac{k^{2}-\xi^{2}}{k^{2}+1}$$
which has singularities at $k=\pm i$, the strips where it is analytic are
$$
-1<k^{\prime \prime}<0 \quad \text { or } \quad 0<k^{\...
- 197
3
votes
1
answer
149
views
Subobject- and factorization-preserving typings
Let $\rightarrowtail$ denote a monomorphism.
Given a morphism $A \stackrel{j}{\to} B$, I am interested in the (not necessarily unique) existence of a factorization $A \stackrel{j'}{\rightarrowtail} X \...
- 133
2
votes
0
answers
101
views
Evidence of optimality of sieve algorithms
Sieve techniques apply to integer factoring and discrete logarithm to provide $2^{O(((\log n)(\log\log n)^2)^{1/3})}$ complexity for $n$ bit factoring and $n$ bit prime discrete logarithm.
The state ...
- 12.8k
0
votes
1
answer
146
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 ...
- 2,279
3
votes
0
answers
150
views
The kronecker symbol and factorization of $n=\frac{B^N-1}{B-1}$
Let $n=\frac{B^N-1}{B-1}$. Assume $n$ is congruent to 3 modulo 4.
We have the following:
If $N$ is 1 modulo 4, then $N$ is quadratic residue modulo $n$
and $-N$ is quadratic non-residue. The square ...
- 23.3k
0
votes
1
answer
71
views
Factorization of a polynomial involving cosine into $m$ second-order factors [closed]
For each $m\in\mathbb{N}$ and fixed $a>0,\theta\in\mathbb{R}$, I want to factorizate the polynomial $p_m(x) = x^{2m} - 2a^m\cos (m\theta)x^m + a^{2m}$ into $m$ polynomials of second order. Using ...
- 373
7
votes
0
answers
136
views
Factor-counting sequence
Define a non-negative integer sequence $\{\mathcal{F}_n\}$ as follows: start with 1 and, at each step, insert the number of entries already present in the sequence which are factors of the last one.
...
- 3,053
0
votes
0
answers
105
views
Can factorization of very large numbers be aided by associating them with a series (described below) of quadratic polynomials?
My name is J. Calvin Smith. I graduated in 1979 with a Bachelor of Arts in Mathematics from Georgia College in Milledgeville, Georgia. My Federal career (1979-2012) in the US Department of Defense led ...
-1
votes
3
answers
118
views
Are <sum, product, N> triplets unique and hard to solve? [closed]
This question comes from some reasoning I made myself about a "joke block chain" where every new block is labeled with a triplet <S, P, N> where where S = sum of the N transactions so ...
- 109
5
votes
2
answers
280
views
Updates on a least prime factor conjecture by Erdos
In the 1993 article "Estimates of the Least Prime Factor of a Binomial Coefficient," Erdos et al. conjectured that
$$\operatorname{lpf} {N \choose k} \leq \max(N/k,13)$$
With finitely many ...
2
votes
1
answer
161
views
For an integral domain $R$ when does $a^2 \equiv b^2 \bmod 4R$ imply $a \equiv b \bmod 2R$?
Suppose we have $a^2 \equiv b^2 \bmod 4R$ where $R$ is an integral domain. Under what conditions on $R$ can we conclude that $a \equiv b \bmod 2R$?
This would hold if $2 \in R$ is a prime or the ...
- 97
1
vote
0
answers
49
views
Probability of factor of particular size
What is the probability that an integer $a$ picked uniformly in $[t/2,t]$ has a factor in $[t^{\alpha},2t^{\alpha}]$ where $\alpha\in(0,1)$? I am interested when $\alpha=1/3$ but if there is a general ...
- 1,708
0
votes
1
answer
95
views
Could prime factorization of n!+1 using the general number field sieve be said to take subfactorial time?
I am interested in the prime factorization using the general number field sieve. This method is said to take subexponential time relative to the number of bits in a number. (Other algorithms are ...
- 101