2
$\begingroup$

I posed a question called "A Product Related to Unrestricted Partitions". As it stands it is too hard. Here's another variation which is easier to search for and hopefully might shed some light on the harder problem..

Begin with the generating function for unrestricted partitions written out as follows:

$$\frac{1+x+x^2+x^3+\dots}{(1-x^2)(1-x^3)(1-x^4)\cdots}$$

Now change some of the signs in these factors. Is it possible that the resulting series has coefficients all of which are +1, -1, or zero? Failing this, what is the longest solution with coefficients +1, -1, or zero that can be found?

$\endgroup$

1 Answer 1

3
$\begingroup$

I've established by brute-force that it is not possible to get a series with $\{-1,0,1\}$ coefficients this way. The maximum one can get is having such coefficients for degrees up to 121. Here is one example that achieves this many $\{-1,0,1\}$ coefficients:

Numerator:

1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 - x^8 - x^9 - x^10 - x^11 - x^12 - x^13 - x^14 - x^15 - x^16 - x^17 - x^18 - x^19 - x^20 - x^21 - x^22 - x^23 - x^24 - x^25 - x^26 - x^27 - x^28 - x^29 - x^30 - x^31 + x^32 + x^33 + x^34 + x^35 + x^36 + x^37 + x^38 + x^39 + x^40 + x^41 + x^42 + x^43 + x^44 + x^45 + x^46 + x^47 + x^48 + x^49 + x^50 + x^51 + x^52 + x^53 + x^54 + x^55 + x^56 + x^57 + x^58 - x^59 + x^60 - x^61 + x^62 - x^63 - x^64 - x^65 - x^66 + x^67 + x^68 - x^69 + x^70 + x^71 + x^72 + x^73 + x^74 + x^75 + x^76 + x^77 + x^78 - x^79 - x^80 - x^81 - x^82 - x^83 - x^84 - x^85 + x^86 + x^87 - x^88 + x^89 + x^90 - x^91 + x^92 - x^93 - x^94 - x^95 + x^96 - x^97 - x^98 - x^99 + x^100 + x^101 - x^102 + x^103 + x^104 + x^105 - x^106 - x^107 + x^108 - x^109 + x^110 + x^111 - x^112 - x^113 + x^114 - x^115 + x^116 - x^117 - x^118 + x^119 - x^120 + x^121 + O(x^122)

Denominator:

(1+x^2)*(1+x^3)*(1+x^4)*(1+x^5)*(1+x^6)*(1-x^7)*(1+x^8)*(1-x^9)*(1+x^10)*(1+x^11)*(1+x^12)*(1+x^13)*(1+x^14)*(1-x^15)*(1+x^16)*(1-x^17)*(1+x^18)*(1+x^19)*(1+x^20)*(1+x^21)*(1+x^22)*(1-x^23)*(1+x^24)*(1-x^25)*(1+x^26)*(1+x^27)*(1+x^28)*(1+x^29)*(1+x^30)*(1-x^31)*(1+x^32)*(1-x^33)*(1+x^34)*(1+x^35)*(1+x^36)*(1+x^37)*(1+x^38)*(1-x^39)*(1+x^40)*(1-x^41)*(1+x^42)*(1+x^43)*(1+x^44)*(1+x^45)*(1+x^46)*(1-x^47)*(1+x^48)*(1-x^49)*(1+x^50)*(1+x^51)*(1+x^52)*(1+x^53)*(1+x^54)*(1-x^55)*(1+x^56)*(1-x^57)*(1+x^58)*(1-x^59)*(1+x^60)*(1+x^61)*(1+x^62)*(1-x^63)*(1+x^64)*(1-x^65)*(1+x^66)*(1+x^67)*(1+x^68)*(1+x^69)*(1+x^70)*(1-x^71)*(1+x^72)*(1-x^73)*(1+x^74)*(1+x^75)*(1+x^76)*(1+x^77)*(1+x^78)*(1-x^79)*(1+x^80)*(1-x^81)*(1+x^82)*(1-x^83)*(1+x^84)*(1+x^85)*(1+x^86)*(1-x^87)*(1-x^88)*(1+x^89)*(1+x^90)*(1-x^91)*(1+x^92)*(1+x^93)*(1+x^94)*(1-x^95)*(1-x^96)*(1+x^97)*(1+x^98)*(1-x^99)*(1+x^100)*(1+x^101)*(1-x^102)*(1+x^103)*(1-x^104)*(1+x^105)*(1-x^106)*(1-x^107)*(1+x^108)*(1+x^109)*(1-x^110)*(1-x^111)*(1-x^112)*(1+x^113)*(1-x^114)*(1+x^115)*(1-x^116)*(1+x^117)*(1-x^118)*(1-x^119)*(1+x^120)*(1-x^121) + O(x^122)

Resulting series:

1 + x - x^3 - x^4 - x^5 - x^6 + x^7 - x^12 - x^13 + x^14 + x^16 + x^17 + x^18 - x^20 + x^23 + x^24 - x^29 + x^32 + x^33 - x^35 - x^36 - x^37 - x^38 + x^39 + x^41 - x^43 - x^44 + x^48 + x^49 - x^51 - x^52 - x^53 - x^54 + x^56 + x^60 - x^61 - x^63 + x^67 - x^68 + x^69 + x^71 + x^72 + x^73 - x^76 + x^77 + x^81 + x^82 + x^83 - x^85 + x^87 - x^88 - x^89 + x^90 - x^91 + x^92 - x^93 - x^95 - x^99 - x^102 - x^104 + x^105 + x^107 - x^111 - x^114 + x^115 + x^118 - x^119 + x^121 + O(x^122)

P.S. It can be seen that in any series obtained this way, the coefficient of $x^n$ is congruent to $p(n)$ modulo 2. Hence, when the coefficient of $x^n$ belongs to $\{-1,0,1\}$, it is zero if and only if $n$ belongs to https://oeis.org/A001560


Here is my PARI/GP code for the brute-force:

{ test2(n,p,m) = my(q,t); if(n>=r, r=n;print(r-1," ",vecextract(s,2^(r-1)-1)); ); for(j=0,1, q=p/(1+(-1)^j*x^n); for(i=0,1, if( abs( polcoeff((m+(-1)^i*x^n + O(x^(n+1)))*q,n) )<=1, s[n]=[(-1)^i,(-1)^j]; test2(n+1,q,m+(-1)^i*x^n)); )); }
s=vector(130); r=0; test2(2,1+O(x^131),1+x)

It tries to extend solutions by adding large and large powers and prints out current records as vectors of pairs of signs (one for numerator, one for denominator) for each degree. The series precision bound of 130 is chosen knowing that the degree won't go above 122 (otherwise it would raise an exception in PARI/GP).

$\endgroup$
7
  • $\begingroup$ Why it is not possible? $\endgroup$ Sep 27, 2017 at 12:33
  • $\begingroup$ @FedorPetrov: I've brute-forced this. One of the maximum solutions is given above. $\endgroup$ Sep 27, 2017 at 12:36
  • $\begingroup$ But on the first glance there are too many variants to check. $\endgroup$ Sep 27, 2017 at 12:38
  • $\begingroup$ @FedorPetrov: en.wikipedia.org/wiki/Backtracking $\endgroup$ Sep 27, 2017 at 12:42
  • $\begingroup$ @MaxAlekseyev Thank you for this. How long did your search for the maximal series take? Could you provide me with the program? Your solution with degree 121 is better than I ever found. The next logical thing to try by way of a search is to write 1/(1-x^2) as 1+x^2+x^4+...before changing the signs. $\endgroup$ Sep 27, 2017 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.