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

187
questions

**0**

votes

**0**answers

149 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$$\...

**1**

vote

**0**answers

81 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^{\...

**0**

votes

**0**answers

29 views

### Asymptotics of a sum involving multiplicative partitions of an integer $n$ into $k$ possibly non-distinct parts $≥2$

Let $x\in\left(0,1\right)$. For each integer $n\geq2$, let $\Omega\left(n\right)$ denote the number of prime factors of $n$, counted according to multiplicities; thus $\Omega\left(2\right)=1$, $\Omega\...

**2**

votes

**1**answer

102 views

### Are there any homomorphic analog error correction code?

Are there any analog error correction codes that are additively and multiplicatively homomorphic?

**1**

vote

**0**answers

57 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^{\...

**3**

votes

**1**answer

135 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 \...

**2**

votes

**0**answers

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

**0**

votes

**1**answer

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

**3**

votes

**0**answers

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

**0**

votes

**1**answer

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

**7**

votes

**0**answers

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

**0**

votes

**0**answers

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

**0**

votes

**0**answers

46 views

### Irreducibility of positive semidefinite polynomial

A polynomial $f \in \mathbb{R}[X]$ is positive semidefinite, i.e. $f(x)\geq 0$ for all $x\in \mathbb{R}$, if and only if it is a sum of two squares of real polynomials, i.e. $f=g^2+h^2$ for $g,h \in \...

**-1**

votes

**3**answers

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

**5**

votes

**2**answers

274 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

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

**1**

vote

**0**answers

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

**0**

votes

**1**answer

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

**1**

vote

**0**answers

105 views

### Primes which do not divide certain homogeneous polynomials

It is known that if $x^2 + y^2 = z^2$ is a primitive Pythagorean triplet then $z$ is not divisible by any prime of the form $4k-1$. The following is a generalization of this classical result which ...

**2**

votes

**0**answers

49 views

### How to prove polynomial inequality encoded from 1-factors in $K_{2n}$

Let $G=(V,E)$ be a complete graph $K_{2n}$ and it has $m$ 1-factors $f_{i,(i=1,\dots,m)}$, where $m=\frac{(2n)!}{n!2^n}$.
Some definition:
$F=\{f_{1},f_{2},...,f_{2n-1}\}$ is one 1-factorization in $...

**3**

votes

**0**answers

256 views

### If $p^2 - q^2$ is a perfect square where $p$ and $q$ are primes $> 5000$ then is one of its prime factors always greater than $17$? [closed]

Is it true that if $p^2 - q^2$ is a perfect square where $p$ and $q$ are primes $> 5000$ then it has a prime factor greater than $17$?
Note: This question was asked in MSE but did not receive an ...

**2**

votes

**1**answer

56 views

### Matrix factorization for dimensional reduction similar to spectral decomposition/SVD

I have a graph clustering problem I'm working on and it basically involves finding a factorization of the adjacency matrix $A$ such that the following equations are (approximately) satisfied:
$$
A \...

**1**

vote

**1**answer

140 views

### Around a characterization for even perfect numbers, similar than Euclides-Euler theorem, in terms of totatives

In this post we denote the sum of divisors function as $$\sigma(n)=\sum_{1\leq d\mid n}d,$$ then an even perfect number is a positive integer $n\equiv 0\text{ mod }2$ for which $\sigma(n)=2n.$ As ...

**2**

votes

**1**answer

187 views

### Equations involving arithmetic functions of primorials

Let $\sigma(n)=\sum_{1\leq d\mid n}d$ the sum of divisors, $\varphi(n)$ the Euler's totient function and we denote the primorial $\prod_{k=1}^n p_k$ as $N_n$, where $p_k$ denotes the $k$-th prime ...

**4**

votes

**0**answers

157 views

### Near Pochhammer symbols: the equation $(n)_m-(k)_l=2$ for integers greater than or equal to two

In this post I consider the following equation involving Pochhammer symbols,
$$(n)_m-(k)_l=2\tag{1}$$
for positive integers $n\geq 2$ and $k\geq 2$, and positive integers $m\geq 2$ and $l\geq 2$.
...

**2**

votes

**1**answer

153 views

### Factorizing a bivariate polynomial

I have a bivariate polynomial for each $n=0,1,2...$
$$
f_n(x,y)=\sum _{k=0}^n \frac{(-1)^k}{2 k+1} \binom{n}{k} \left(x ^2-y ^2\right)^{2 n-2 k}\left([y ( x^2 -1) +x(1 -y^2 )]^{2 k+1}\\ \qquad\qquad\...

**3**

votes

**1**answer

108 views

### Subexponential algorithms that apply only one of factoring and discrete logarithm?

Shor (quantum polynomial), Number Field Sieve (subexponential), Pollard rho (square root) all have both factoring and discrete logarithm over $\mathbb F_p^*$ variants.
What are the subexponential ...

**3**

votes

**1**answer

82 views

### Irreducible skew polynomials over an algebraically closed field

Let $\mathbb{F}$ be a field, and denote with $\mathbb{F}[t,\sigma]$ the skew-polynomial ring, where $\sigma$ is an automorphim of $\mathbb{F}$. Recall that the multiplication of this ring is defined ...

**5**

votes

**0**answers

393 views

### Factorizations as a product of primes minus one

Let $x$ be a positive rational number. I am interested in factorizing $x$ as a product of primes minus one. In fact, I would also like make sure the primes in the decomposition are distinct, and I ...

**2**

votes

**0**answers

175 views

### Heuristic for lower bounding the time for integer factorization?

I am posting this question here in hope that someone finds this heuristic useful, and maybe someone with more experience will make use of this:
As @GerryMyerson suggested here is a statement of what ...

**8**

votes

**0**answers

138 views

### A factorization game

This is a toy version of a problem I have posted recently.
Imagine playing the following game. You choose a polynomial $B$ over a finite field $\mathbb F_p$, of degree $\deg B\le p-1$ (where $p$ is a ...

**3**

votes

**1**answer

126 views

### Factoring $x^p H(x) + x^q B(x) + T(x)$ over a finite field

$\newcommand\S{\mathcal S}$
Let $p$ be a prime, and suppose that $0.9(p-1)<q<p-1$. Suppose, furthermore, that $H,B,T\in\mathbb F_p[x]$ satisfy $\max\{\deg H,\deg T\}\le q-1$ and $\deg B\le p-1-q$...

**2**

votes

**1**answer

180 views

### Proving largest power of $(a^2-ab+b^2)$ that divides $a^p-b^p-(a-b)^p$ for odd prime $n$

It is obvious that for odd $n \in \Bbb N$, $a^n-b^n-(a-b)^n$ is divisible by $ab(a-b)$ (with $n=1$ being a special case in which $a^n-b^n-(a-b)^n$ is zero). This can be viewed as a fact about ...

**20**

votes

**1**answer

2k views

### Circle $x^2 + y^2 = n!$ doesn't hit any lattice points for any $n$ except for $0$, $1$, $2$ and $6$ or does it?

I stumbled across the following problem in high school:$$
x^2 + y^2 = n!
$$
I tested it within my laptop capabilities, watched a 3b1b video Pi in prime regularities, where he explains how to find the ...

**4**

votes

**0**answers

154 views

### Consecutive integers each of which has a large prime factor

There are many results about consecutive integers all having small prime factors. But what about consecutive integers each of which has a large prime factor?
More precisely, let $P(n)$ be the ...

**5**

votes

**1**answer

124 views

### Density of numbers with multiple factors near square root

Fix constants $1\leq \alpha<\beta$. What is the density of the set of positive integers $n$ with at least two factors between $\alpha\sqrt{n}$ and $\beta\sqrt{n}$?
(I am specifically interested ...

**0**

votes

**1**answer

310 views

### Reason Coppersmith fails here?

Take classic problem of finding $P,Q$ in balanced semi-prime $N=PQ$.
$P$ has a binary expansion and so does $Q$. We can set the binary $0/1$ variables to be $x_1$ through $x_{\lceil\log P\rceil}$ and $...

**1**

vote

**1**answer

134 views

### Factoring with partial information on gaps

If $N=PQ$ is a semi-prime with $P=N^{\frac12 +\delta}$ and $Q=N^{\frac12-\delta}$ then if we know $\delta\in(0,\frac12)$ to a reasonable precision we can factor $N$ quickly. What precision (number of ...

**1**

vote

**1**answer

63 views

### Generalizing cycle/pseudo-tree factorizations for permutations/transformations to arbitrary binary relations

It's well known every permutation has a unique factorization into disjoint cycles (up to a re-ordering of these factors since they commute), while similarly it can be shown that every transformation ...

**2**

votes

**0**answers

99 views

### Coppersmith's method to quadrivariate degree $2$ polynomials that behave as bivariate?

We have a polynomial $f(x_1,x_2,x_3,x_4)\in\mathbb Z[x_1,x_2,x_3,x_4]$ where the only monomials are either from set $$\{x_1,x_1x_2,x_2,x_3,x_3x_4,x_4\}$$ and we seek solutions $(x_1,x_2,x_3,x_4)\in\...

**4**

votes

**1**answer

246 views

### Is total degree version and $x,y$ degree version of Coppersmith's theorem correct?

The notes here https://web.eecs.umich.edu/~cpeikert/lic13/lec04.pdf have the note 'Small decryption exponent $d$: so far the best known attack recovers $d$ if it is less than $N^{.292}$. This uses a ...

**5**

votes

**1**answer

174 views

### $\{ P_3, P_4 \}$-factor

Definition. A graph $G=(V,E)$ is to be $\{d_1,\dots,d_n\}$-graph if for each vertex $v\in V$ we have $\text{deg}(v)=d_i$ for some $i=1,\dots n$.
Definition. A connected graph $G=(V,E)$ is called $...

**-1**

votes

**1**answer

144 views

### The power of a prime in the prime factorization of a factorial [closed]

How do we find—for example—how many $5$s are in the prime factorization of $n!$? I've read that it is $\lfloor n/5 \rfloor$, but why is that?

**5**

votes

**1**answer

137 views

### Finding a particular matrix factor

Consider the following Laurent polynomial matrix-valued function in the variable $x\in\mathbb{C}$
$$
A(x) = \begin{bmatrix} 0 & x \\ x^{-1} & 0\end{bmatrix}.
$$
I'm interested in finding a ...

**3**

votes

**0**answers

234 views

### Can we efficiently factor $n$ given that $n=pq$ where $p,q$ are primes satisfying $p=a^2+b^2, q=2ab+1$ for some $a,b$

Suppose we're given a particular number $n \in \mathbb{N}$.
We're also given that $n=pq$ where $p,q$ are unknown primes satisfying
$$
p=a^2+b^2
$$ and
$$
q=2ab+1
$$
for some $a,b$.
Is there an ...

**3**

votes

**2**answers

145 views

### Factoring certain Hessians of real homogeneous bivariate polynomials

For any homogeneous polynomial $f \in \mathbb R [x,y]$, define the homogeneous polynomial
$$H(f) := \partial_yf^2\partial_x\partial_xf-2\partial_xf\partial_yf\;\partial_x\partial_yf+\partial_xf^2\...

**5**

votes

**2**answers

207 views

### Factoring a positive semidefinite matrix into binary matrices

This question is motivated by a research problem I recently encountered. Consider two sets of random variables $\mathbf{X}$ and $\mathbf{Y}$, where $\mathbf{Y}$ can be expressed as a linear ...

**2**

votes

**0**answers

150 views

### List of analytically known eigensystems?

In condensed matter physics, we often come across matrices that are multi-diagonal or banded. For example, I may have a matrix with three tridiagonal bands, or a tridiagonal band and two/four ...

**2**

votes

**2**answers

750 views

### What is the natural density of hyper prime numbers?

What do we mean by hyper prime numbers? Well, roughly speaking they are natural numbers which are prime with respect to hyperoperators in arithmetic such as exponentiation, tetration, pentation, et ...

**33**

votes

**7**answers

2k views

### On the polynomial $\sum_{k=0}^n\binom{n}{k}(-1)^kX^{k(n-k)}$

Let $n = 2m$ be an even integer and let $F_n(X)$ be the polynomial $$F_n(X):=\sum_{k=0}^n\binom{n}{k}(-1)^kX^{k(n-k)}.$$ I observed (but cannot prove) that the polynomial $F_n$ is always divisible by $...