1
$\begingroup$

The goal of this problem is to see if there is a structured way to factor numbers constructed from a set of distinct odd primes $p_1$ through $p_n$ in a number ring.

Take an arbitrary non empty subset $\mathcal I$ of $\{1,\dots,n\}$ and let $P_{\mathcal I}=2\prod_{i\in I}p_i+1$.

Is there an algebraic extension $\Bbb Z[\alpha_1,\dots,\alpha_m]$ of $\Bbb Z$ such that there exists $t$ elements (possibly indistinct) $a_j\in\Bbb Z[\alpha_1,\dots,\alpha_m]$ for $j\in\{1,\dots,t\}$ such that for every $\mathcal I\subseteq\{1,\dots,n\}$ there is a subset $\mathcal J$ from $\{1,\dots,t\}$ such that $P_{\mathcal I}=2\prod_{i\in I}p_i+1=\prod_{j\in\mathcal J}a_j$ holds?

If so how big is least $t$ and $m$ compared to $n$ and how big are norms of $a_j$?

I think $t=O(n)$ and $|a_j|=O(n)$ (where $|a_j|$ is norm of $a_j$) could be possible.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Could you write your question in plain English instead of using three nested quantifiers? That is, could you write the question in a manner that conveys how you really came across it? $\endgroup$
    – KConrad
    Jun 23, 2016 at 5:19
  • $\begingroup$ @KConrad I just want to know if there is an way to split combinatorially structured set of products in a number ring so that the resulting product has a nice structure. $\endgroup$
    – user94040
    Jun 23, 2016 at 6:27
  • $\begingroup$ Can't you just take $t = 2^n$ (corresponding to $\mathcal P(\{1,\ldots,n\})$) and have each $a_j$ be equal to a $P_I$ (i.e. $J$ is always a singleton)? $\endgroup$
    – R. van Dobben de Bruyn
    Jun 23, 2016 at 7:00
  • $\begingroup$ So you claim $t=2^n$ is the least $t$ we can have? $\endgroup$
    – user94040
    Jun 23, 2016 at 7:12

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.