3
$\begingroup$

Hello Mathematica StackExchange community,

I'm hoping that someone can be of help!

Let p be a fixed prime. I have a multivariable polynomial g (of degree t). I need a list of all the monomial terms of g which satisfy:

  1. Degree of the monomial term is t.
  2. Each of the exponents in the monomial term is less than or equal to p-2

I have been playing around with the Mathematica commands (MonomialList, Coefficient, CoefficientRules, Expand, etc.), but have not been successful in reaching my goal.

If anybody can provide some help, it is greatly appreciated! Thank you in advance.

Sincerely, Richard M. Low

UPDATE:---------------------------------

Due to kglr's help, I have been able to make some progress on my problem. Here is kglr's original Mathematica code: 

ClearAll[x, y, z, f]
t = 4;
p = 5;
poly = (x + 2 y + z)^t + x^2;

f = Select[And[Total@# == t, Max[#] <= p - 2] &@Exponent[#, {x, y, z}] &];

selected = f@MonomialList[poly]

I'm hoping that kglr (or somebody else) can help me modify it slightly.

Since the typical polynomials that I will be working with may have (literally) billions (~ 6^14) of monomial terms, I would like for the output of f to be 1 monomial term (not the entire list) which satisfies the two conditions (in my original post) AND whose coefficient is not equal to 0 (mod p).

This will greatly decrease the runtime and memory usage of the Mathematica program. The runtime of the original Mathematica program went past several days and I ended up aborting the calculation.

Again, I appreciate any help that the Mathematica StackExchange can provide. I am completely incompetent in Mathematica programming.

Thank you in advance.

Sincerely, Richard M. Low

Improve this question
$\endgroup$
5
$\begingroup$ 
ClearAll[x, y, z, f]
t = 4;
p = 5;
poly = (x + 2 y + z)^t + x^2;

f = Select[And[Total@# == t, Max[#] <= p - 2] &@Exponent[#, {x, y, z}] &];

selected = f @ MonomialList[poly]

{8 x^3 y, 4 x^3 z, 24 x^2 y^2, 24 x^2 y z, 6 x^2 z^2, 32 x y^3, 48 x y^2 z, 24 x y z^2, 4 x z^3, 32 y^3 z, 24 y^2 z^2, 8 y z^3}

Complement[MonomialList @ poly, selected]

{x^2, x^4, 16 y^4, z^4}

Update: "I would like for the output of f to be 1 monomial term (not the entire list) which satisfies the two conditions."

Just replace Select with SelectFirst:

f2 = SelectFirst[And[And[Total@# == t, Max[#] <= p - 2] &@Exponent[#, {x, y, z}], 
  Mod[# /. x | y | z -> 1, p] != 0] &]

selected2 = f2@MonomialList[poly]

8 x^3 y

Update 2: A faster approach: use Expand instead of MonomialList:

f2 @ Expand[poly]

8 x^3 y

Improve this answer
$\endgroup$
12
  • $\begingroup$ kglr, I think that your Mathematica code works! Let me try some initial tests to see what happens. I'll get back to you very soon! Thanks again and I'll report back my findings. $\endgroup$ – richmlow Feb 14 '20 at 10:42
  • $\begingroup$ Your Mathematica code works! Thank you very much for your help! $\endgroup$ – richmlow Feb 14 '20 at 11:23
  • $\begingroup$ I am hoping that kglr's Mathematica code can be slightly modified. Please see the UPDATE in my original post. $\endgroup$ – richmlow Feb 22 '20 at 6:18
  • $\begingroup$ kglr, Thank you for the suggestion of replacing with "SelectFirst". What about checking that the monomial term has coefficient not equal to 0 (mod p), before outputting the desired monomial term? Where should I put the "Mod p" check condition? $\endgroup$ – richmlow Feb 22 '20 at 23:48
  • $\begingroup$ @richmlow, please see the update. $\endgroup$ – kglr Feb 23 '20 at 0:02
0
$\begingroup$

It is also possible to use the output of CoefficientRules[] to get what is wanted. To wit,

With[{t = 4, p = 5},
     KeyValueMap[#2 Inner[Power, {x, y, z}, #1, Times] &, 
                 KeySelect[CoefficientRules[(x + 2 y + z)^t + x^2, {x, y, z}], 
                           Tr[#] == t && Max[#] <= p - 2 &]]]
   {8 x^3 y, 4 x^3 z, 24 x^2 y^2, 24 x^2 y z, 6 x^2 z^2, 32 x y^3, 48 x y^2 z,
    24 x y z^2, 4 x z^3, 32 y^3 z, 24 y^2 z^2, 8 y z^3}

To add in the further $\bmod p$ restriction, you can use another call to Select[]:

With[{t = 4, p = 5},
     KeyValueMap[#2 Inner[Power, {x, y, z}, #1, Times] &, 
                 Drop[Select[KeySelect[CoefficientRules[(x + 2 y + z)^t + x^2,
                                                        {x, y, z}], 
                                       Tr[#] == t && Max[#] <= p - 2 &],
                             ! Divisible[#, p] &], {2, -1}]]]
   {8 x^3 y}

where I use the explicit test Divisible[] for filtering.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Hello J.M., Thank you for giving an alternative Mathematica program in answering my original question! Right now, SJSU is in the middle of Final Exam week. So, I haven't had a chance to look at your program. However, this is at the top of my "To Do" list! Thank you again and I'll be in touch with you (via this StackExchange thread) soon. $\endgroup$ – richmlow May 13 '20 at 21:52
  • $\begingroup$ Hello J.M., Your alternate Mathematica program also helped in answering my original question. Thank you for your help and generosity! $\endgroup$ – richmlow Jan 20 at 12:39

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.