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
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\...
user avatar
  • 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\...
user avatar
  • 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 (...
user avatar
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 ...
user avatar
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)...
user avatar
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 ...
user avatar
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. ...
user avatar
  • 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]...
user avatar
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 ...
user avatar
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) ...
user avatar
  • 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\...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 $\...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 \...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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{...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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\...
user avatar
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$ ...
user avatar
  • 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 $>...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
  • 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 ...
user avatar
  • 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$$\...
user avatar
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^{\...
user avatar
  • 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?
user avatar
  • 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^{\...
user avatar
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 \...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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. ...
user avatar
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 ...
user avatar
-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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar

1
2 3 4 5