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
0
votes
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
3answers
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
2answers
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
2answers
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
2answers
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
0answers
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
2answers
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
7answers
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 $...