วิธีค้นหาจำนวนฟังก์ชันพหุนามที่แตกต่างจาก $\mathbb{Z}_2$ ถึง $\mathbb{Z}_2$เหรอ? [ซ้ำ]
สำหรับจำนวนเต็มบวกใด ๆ $n$พหุนามมีกี่องศา $n$ เกิน $\mathbb{Z}_2$เหรอ? จำนวนฟังก์ชันพหุนามที่แตกต่างจากฟังก์ชัน$\mathbb{Z}_2$ ถึง $\mathbb{Z}_2$เหรอ?
ความพยายาม: ส่วนแรกชัดเจนสำหรับฉันตั้งแต่มี $2$ ทางเลือกสำหรับแต่ละค่าสัมประสิทธิ์และมี $n$ ค่าสัมประสิทธิ์จึงมี $2^n$พหุนามดังกล่าว ฉันมีปัญหาในการทำความเข้าใจส่วนที่สองซึ่งฉันต้องหาฟังก์ชันพหุนามที่แตกต่างกัน
ถ้าสมมุติ $p(x)$ และ $p'(x)$ เป็นฟังก์ชันพหุนามสองค่าที่เท่ากัน $\mathbb{Z}_2$ ดังนั้น $p(x)=a_nx^n+\cdots+a_0$ และ $p'(x)=a'_nx^n+\cdots+a'_0$แล้ว $p'(x)=p(x)$ สำหรับ $x=0,1$. ดังนั้น$a'_0=a_0$. และเนื่องจากระดับของพหุนามเหล่านี้คือ$n$ แล้ว $a_n=a'_n=1$. ดังนั้นในการหาฟังก์ชันพหุนามที่แตกต่างกันเราต้องพิจารณาเมื่อ$p(x)$ ไม่สามารถเท่ากับ $p'(x)$ สำหรับทุกมูลค่าของ $x\in\{0,1\}$. จากที่นี่ฉันไม่สามารถดำเนินการต่อได้ ฉันกำลังมองหาวิธีแก้ปัญหา ทุกที่ที่ฉันเห็นว่าพวกเขาเริ่มโต้แย้งด้วยความจริงที่ว่ามีเพียง$4$พหุนามดังกล่าวแล้วจึงยกตัวอย่างของพหุนามดังกล่าว ฉันต้องการความช่วยเหลือในการทำความเข้าใจปัญหานี้ ขอขอบคุณ
คำตอบ
มีเพียง 4 ฟังก์ชันที่แตกต่างกัน $f: \Bbb Z_2 \to \Bbb Z_2$. นี่เป็นเพราะจำนวนสมาชิกของชุดฟังก์ชัน$A \to B$ คือ $$|B^A|=|B|^{|A|}$$ เมื่อใดก็ตาม $A,B$ เป็นชุดที่ จำกัด
มันเป็นฟังก์ชันพหุนาม แท้จริงพวกเขาคือ$$f_1(x)=0$$ $$f_2(x)=1$$ $$f_3(x)=x$$ $$f_4(x)=1-x$$ เราได้พบทั้งหมดแล้ว
เกิน $\Bbb{Z}_2$พหุนาม $x(x+1) = x^2 + x$ เหมือนกัน $0$ซึ่งหมายความว่าฉันสามารถแทนที่ $x^2$ ด้วย $x$ในนิพจน์พหุนามใด ๆ และได้รับค่าเดียวกัน ใช้สิ่งนี้ซ้ำ ๆ$\Bbb{Z}_2$พหุนาม $$a_0 + a_1 x + a_2 x^2 + ... + a_n x^n$$ ให้ค่าเดียวกับพหุนามเสมอ $$a_0 + (a_1 + a_2 + a_3 + ... + a_n)x,$$ และมีเพียง $4$ พหุนามที่แยกแยะได้มากกว่า $\Bbb{Z}_2$ขึ้นอยู่กับว่า $a_0 = 0$ หรือ $1$และไม่ว่า $a_1 + a_2 + a_3 + ... +a_n = 0$ หรือ $1$.
คำตอบสำหรับคำถามแรกของคุณควรเป็น $2^{n-1}$ ค่อนข้างมากกว่า $2^{n}$ ตั้งแต่ค่าสัมประสิทธิ์ของ $x^n$ ตลอดเวลา $1$.
สำหรับส่วนที่สองโปรดทราบว่าชุดของฟังก์ชันพหุนามทั้งหมดคือชุดของฟังก์ชันทั้งหมดในกรณีของคุณ
แก้ไข: คำตอบที่ระบุไว้ในความคิดเห็นส่วนแรกของคำตอบนี้ไม่ถูกต้อง