找回密码
 欢迎注册
查看: 15679|回复: 11

[讨论] 以解构造整数多项式方程

[复制链接]
发表于 2020-8-15 21:23:53 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
本帖最后由 zeroieme 于 2020-8-15 21:56 编辑

首先限定多个变量\(\left[x_1,x_2,\ldots,x_m\right]\)每个变量只能取值为0或1。
然后为给定若干个解  \(X_1=\left[x_1=a_{1,1},x_2=a_{1,2}, \ldots ,x_m=a_{1,m}\right],\)\(\ldots\)\(X_n=\left[x_1=a_{n,1},x_2=a_{n,2},\ldots,x_m=a_{n,m}\right]\)  构造一个整数多项式。

简单例子
\(\left\{\left\{x_1,x_2,x_3\right\}=\{1,0,1\},\left\{x_1,x_2,x_3\right\}=\{0,1,0\},\left\{x_1,x_2,x_3\right\}=\{1,1,1\},\left\{x_1,x_2,x_3\right\}=\{1,1,0\}\right\}\)
简单粗暴的办法是\(\left(4 x_1+2 x_2+x_3-7\right) \left(4 x_1+2 x_2+x_3-6\right) \left(4 x_1+2 x_2+x_3-5\right) \left(4 x_1+2 x_2+x_3-2\right)=0\)
如果利用\(\left(1-x_i\right) x_i\)求余可得\(-36 x_2 x_1+24 x_2 x_3 x_1-26 x_3 x_1+36 x_1+35 x_2-23 x_2 x_3+25 x_3-35=0\)

能简化到一次方程吗?而且对于更多变量,上述粗暴方法也不管用了。




不能简化到一次方程,方程组也可以

补充内容 (2020-8-18 12:03):
用几何思维,解域为0-1就是n维空间下超立方体的顶点,线性方程至多是n-1维的超平面。

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-8-15 21:56:18 | 显示全部楼层
你在想什么?
直接把全部x1+x2+...+xm-a1-a2-...-am乘起来不好吗?
至于一次,一次肯定不行啊
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-8-15 22:09:43 | 显示全部楼层
本帖最后由 zeroieme 于 2020-8-15 22:26 编辑
.·.·. 发表于 2020-8-15 21:56
你在想什么?
直接把全部x1+x2+...+xm-a1-a2-...-am乘起来不好吗?
至于一次,一次肯定不行啊


在0-1解域下\((a+2 b+4 c+8 d-15) (a+2 b+4 c+8 d-12) (a+2 b+4 c+8 d-3) (a+2 b+4 c+8 d)=0\)

\(384 a b c d-192 a b c-192 a b d+142 a b-192 a c d+164 a c+40 a d-77 a-192 b c d+220 b c-40 b d-65 b-368 c d+88 c+280 d=0\)
与\((a-b)+4 (c-d)=0\)是同解的。
当然这是我构造的,而且我不会逆算。


简单的说是想把逻辑运算线性化。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-8-16 01:19:24 | 显示全部楼层
.·.·. 发表于 2020-8-15 21:56
你在想什么?
直接把全部x1+x2+...+xm-a1-a2-...-am乘起来不好吗?
至于一次,一次肯定不行啊


这样肯定不同解呀,xi, xj可两两交换了,可能产生 m!-1 个增根。

点评

当时我并没有从“然后为给定若干个解...构造一个整数多项式”这句话读出增根的意思……所以很费解  发表于 2020-8-16 05:59
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-8-16 05:58:39 | 显示全部楼层
zeroieme 发表于 2020-8-15 22:09
在0-1解域下\((a+2 b+4 c+8 d-15) (a+2 b+4 c+8 d-12) (a+2 b+4 c+8 d-3) (a+2 b+4 c+8 d)=0\)

\( ...

如果这样我大概明白了

然而问题是

0-1规划好像是个NPC问题
就算你构造出方程,你也得不到(一般的)解法
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-8-16 07:13:24 | 显示全部楼层
主要是你的简化目的不是很明确,不明白你到底要怎么样的结果。
比如你顶楼的例子中,四个向量可以用四个一次多项式的乘积达到目的。是不是希望次数能够尽量低一些?
那么我们首先必然可以找出一个一次多项式满足前两个向量,而且第三个向量是前两个的线性组合,于是这个一次多项式或同时满足前三个向量。
然后再找一个满足第四个向量的多项式,最后两个多项式相乘即可。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-8-16 07:18:32 | 显示全部楼层
当然正常情况一次多项式肯定是不行的,除非给出的所有向量之间本身线性相关。
还要看你的向量数目和向量的维数n之间的关系。
比如向量数目小于n,那么必然可以找出一个一次多项式同时满足它们。
如果向量数目大于n但是小于n(n+1)/2,可以考虑对于每个向量计算出"扩展向量"
x1,x2,...,xn,x1x2,x1x3,...,x1xn,x2x3,...,x2xn,....,x{n-1}x_n
然后必然可以在这个“扩展向量”的空间中找出一种让它们线性组合为0的方案,对应到原向量空间就是一个二次多项式。
当然,这个计算量在向量数目很大时是很困难的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-8-16 08:02:43 | 显示全部楼层
mathe 发表于 2020-8-16 07:13
主要是你的简化目的不是很明确,不明白你到底要怎么样的结果。
比如你顶楼的例子中,四个向量可以用四个一 ...

我的目的是把四个向量作为解构造出一个多项式方程或者方程组。
顶楼是我的一个不太成功的办法。


看3#
\(\{\{a= 0,b= 0,c= 0,d= 0\},\{a= 0,b= 0,c= 1,d= 1\},\{a= 1,b= 1,c= 0,d= 0\},\{a= 1,b= 1,c= 1,d= 1\}\}\)
用顶楼的办法得到一个4次方程,但其实有一个简单的1次方程。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-8-16 08:09:41 | 显示全部楼层
mathe 发表于 2020-8-16 07:13
主要是你的简化目的不是很明确,不明白你到底要怎么样的结果。
比如你顶楼的例子中,四个向量可以用四个一 ...

如果期望次数能够尽量低,那么向量数目小于n的方法是怎样的?至少我可以把向量分成n-1个一组分别算出一次方程。

点评

是的,n-1个点确定一个n-1维超平面  发表于 2020-8-16 14:38
就是n维空间下的n-1维超平面吗?  发表于 2020-8-16 11:41
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 13:12 , Processed in 0.057921 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表